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 in combinatorics. We identify barriers for progress and propose new techniques to circumvent these. (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 $\mathbb{F}_2^n \times \mathbb{F}_2^n$ of size $3.16^{n-o(n)}$, which improves the previous lower bound $2.82^n$ of Linial, Pitassi and Shraibman (ITCS 2018). In the Eval problem over a group $G$, three players need to determine whether their inputs $x_1, x_2, x_3 \in G$ sum to zero. As a consequence of our construction of corner-free sets, the communication complexity of the Eval problem over $\mathbb{F}_2^n$ is at most $0.34n + O(\log n)$, which improves the previous upper bound $0.5n + O(\log n)$. (2) We point out how induced matchings in hypergraphs pose a barrier for existing tensor tools (like slice rank, subrank, analytic rank, geometric rank and G-stable rank) to effectively upper bound the size of independent sets in hypergraphs. This implies a barrier for these tools to effectively lower bound the communication complexity of the Eval problem over any group $G$. (3) We introduce the symmetric subrank of tensors as a proposal to circumvent the induced matching barrier and we introduce the symmetric quantum functional as a symmetric variation on the quantum functionals (STOC 2018). We prove that Comon's conjecture holds asymptotically for the tensor rank, the subrank and the restriction preorder, which implies a strong connection between Strassen's asymptotic spectrum of tensors and the asymptotic spectrum of symmetric tensors.
翻译:我们开发并应用新的组合和振动工具, 以理解多党交流的复杂性。 在 Forehead (NOF) 模型中, 我们发现进步的障碍, 并提出新的方法来绕过这些。 (1) 我们引入了一种技术, 通过组合变换在高压中建造独立设置。 特别是, 我们通过证明存在一个没有角的子集$\masvalb{ F ⁇ 2 ⁇ n\ times\mathb{ F ⁇ 2} F ⁇ 2n$ 独立度3.16 ⁇ n- o(n)$, 相关的Ramsty 类型问题。 有效地改进了以前较低的约束值 2.82美元 利亚尔、 Pitassi 和 Shraibman( ITS 2018)。 在一个组的 Eval 问题中, 3个玩家需要确定他们的输入值 $_1, x_2, x_3 以G$ 和 g$ 和 以零为基数。 由于我们建立无角的系统, 将 Eval 问题的通信复杂性推介于 $\\ fralterralxx 的 。