Boolean Circuits, Tensor Ranks, and Communication Complexity
Boolean Circuits, Tensor Ranks, and Communication Complexity
复制标题
布尔电路、张量秩和通信复杂性
DOI：
10.1137/s0097539794264809
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
J. Sgall
中科院分区：
文献类型：
--
作者：
P. Pudlák;V. Rödl;J. Sgall
我们研究了两种方法来证明小深度电路的大小的下界，即基于多方通信游戏和代数特征扩展的张量秩和刚度的矩阵的概念的方法。我们的方法是组合的，但我们认为，我们的主要贡献涉及在这方面使用的代数概念（张量秩和刚性）。我们的主要结果如下。
(i)一个用于计算移位的通信游戏的$o（n）$位协议，它也给出了多项式乘法张量的接触秩的上界$o（n^2）$;这反驳了一些早期的假设。一个相关的概率构造给出了一个计算所有排列的上界为O（n）$，以及一个指针跳跃与排列的通信复杂度的上界为O（n\log\log n）$。
(ii)深度为2的某些受限回路的下界，与证明一个超线性的深度回路的大小下界有关;这个界既可以解释为多项式乘法张量刚性的下界，也可以解释为在受限模型中计算移位函数所需通信的下界。
(iii)深度为2的布尔电路上界，用于计算移位，更一般地，所有置换;这表明这样的电路比基于沿沿着顶点不相交路径发送位的模型更有效。
We investigate two methods for proving lower bounds on the size of small-depth circuits, namely the approaches based on multiparty communication games and algebraic characterizations extending the concepts of the tensor rank and rigidity of matrices. Our methods are combinatorial, but we think that our main contribution concerns the algebraic concepts used in this area (tensor ranks and rigidity). Our main results are following.
(i) An $o(n)$-bit protocol for a communication game for computing shifts, which also gives an upper bound of $o(n^2)$ on the contact rank of the tensor of multiplication of polynomials; this disproves some earlier conjectures. A related probabilistic construction gives an $o(n)$ upper bound for computing all permutations and an $O(n\log\log n)$ upper bound on the communication complexity of pointer jumping with permutations.
(ii) A lower bound on certain restricted circuits of depth 2 which are related to the problem of proving a superlinear lower bound on the size of logarithmic-depth circuits; this bound has interpretations both as a lower bound on the rigidity of the tensor of multiplication of polynomials and as a lower bound on the communication needed to compute the shift function in a restricted model.
(iii) An upper bound on Boolean circuits of depth 2 for computing shifts and, more generally, all permutations; this shows that such circuits are more efficient than the model based on sending bits along vertex-disjoint paths.