WEEKLY ACTIVITIES

Communication complexity, corner-free sets and the symmetric subrank of tensors (phần 2)
Người trình bày: Tạ Duy Hoàng ( ENS Lyon)

Thời gian: 9h30, Thứ 5, ngày 15/04/2021

Địa điểm: Phòng 612, nhà A6, Viện Toán học.

Tóm tắt: We develop and apply new combinatorial and algebraic tools to understand multiparty communication complexity in the Number On the Forehead (NOF) model, and related Ramsey type problems. We identify barriers for progress and propose new techniques to circumvent these.

  • Part 1:We introduce a technique for constructing independent sets in hypergraphs via combinatorial degeneration. In particular, we make progress on the corner problem by proving the existence of a corner-free subset of F_2^n times F_2^n of size Ω(3.16n/poly(n))
  • Part 2:  We propose to circumvent this barrier via a new natural notion called the symmetric subrank of tensors, the symmetric version of Strassen’s subrank, and we prove relations and separations for the symmetric subrank. We carry out a representation-theoretic study that leads to the symmetric quantum functional, advancing the theory of quantum functionals (STOC 2018) for symmetric tensors.
  • Finally, we prove that “Comon’s conjecture” holds asymptotically for rank, subrank as well as the restriction preorder. This implies a strong connection between Strassen’s asymptotic spectrum of tensors and the asymptotic spectrum of symmetric tensors.

Joint work with: Matthias Christandl, Omar Fawzi, Jeroen Zuiddam.

Back