ECCC-Report TR08-082https://eccc.weizmann.ac.il/report/2008/082Comments and Revisions published for TR08-082en-usThu, 06 May 2010 17:07:46 +0300
Revision 2
| Multiparty Communication Complexity and Threshold Circuit Size of AC$^0$ |
Paul Beame,
Trinh Huynh
https://eccc.weizmann.ac.il/report/2008/082#revision2We prove an $n^{\Omega(1)}/4^k$ lower bound on the randomized $k$-party communication
complexity of depth 4 AC$^0$ functions in the number-on-forehead (NOF) model for up to $\Theta(\log n)$ players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC$^0$ function for $\omega(\log\log n)$ players. For non-constant $k$ the bounds are larger than all previous lower bounds for
any AC$^0$ function even for simultaneous communication complexity.
Our lower bounds imply the first superpolynomial lower bounds for the simulation of AC$^0$ by MAJ-SYMM-AND circuits,
showing that the well-known quasipolynomial simulations of AC$^0$ by such circuits
due to Allender (1989) and Yao (1990) are qualitatively optimal, even for formulas of small constant depth.
We also exhibit a depth 5 formula in NPc-BPPc for $k$ up to $\Theta(\log n)$ and derive
$\Omega(2^{\sqrt{\log n}/\sqrt{k}})$ lower bound on the randomized $k$-party NOF communication complexity of set disjointness for up to $\Theta(\log^{1/3} n)$ players which is significantly larger than the $O(\log\log n)$ players allowed in the best previous lower bounds for multiparty set disjointness. We prove other strong results for depth 3 and 4 AC$^0$ functions.Thu, 06 May 2010 17:07:46 +0300https://eccc.weizmann.ac.il/report/2008/082#revision2
Revision 1
| Multiparty Communication Complexity and Threshold Circuit Size of ${\sf AC^0}$ |
Paul Beame,
Trinh Huynh
https://eccc.weizmann.ac.il/report/2008/082#revision1We prove an $n^{\Omega(1)}/4^k$ lower bound on the randomized $k$-party communication complexity of depth 4 $\sf{AC}^0$ functions in the number-on-forehead (NOF) model for up to $\Theta(\log n)$ players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any $\sf{AC}^0$ function for $\omega(\log\log n)$ players. For non-constant $k$ the bounds are larger than all previous lower bounds for any $\sf{AC}^0$ function even for simultaneous communication complexity.
Our lower bounds imply the first superpolynomial lower bounds for the simulation of $\sf{AC}^0$ by $\sf{MAJ\circ SYMM\circ AND}$ circuits, showing that the well-known quasipolynomial simulations of $\sf{AC}^0$ by such circuits are qualitatively optimal, even for formulas of small constant depth.
We also exhibit a depth 5 formula in $\cl{NP}^{cc}_k-\cl{BPP}^{cc}_k$ for $k$ up to $\Theta(\log n)$ and derive an $\Omega(2^{\sqrt{\log n}/\sqrt{k}})$ lower bound on the randomized $k$-party NOF communication complexity of set
disjointness for up to $\Theta(\log^{1/3} n)$ players which is significantly larger than the $O(\log\log n)$ players allowed in the best previous lower bounds for multiparty set disjointness. We prove other strong results for depth 3 and 4 $\sf{AC}^0$ functions.
Sat, 22 Aug 2009 21:21:28 +0300https://eccc.weizmann.ac.il/report/2008/082#revision1
Paper TR08-082
| Multiparty Communication Complexity and Threshold Circuit Size of AC^0 |
Paul Beame,
Trinh Huynh
https://eccc.weizmann.ac.il/report/2008/082We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For non-constant k the bounds are larger than all previous lower bounds for any AC^0 function even for simultaneous communication complexity.
Our lower bounds imply the first super-polynomial lower bounds for the simulation of AC^0 by general MAJ-SYMM-AND circuits, showing that the well-known quasi-polynomial simulations of AC^0 by such circuits are qualitatively optimal, even for read-once formulas of small constant depth.
We also exhibit a read-once depth 5 formula in NP^{cc}_k &#8722; BPP^{cc}_k for k up to Theta(log n) and derive an Omega(2^{(log n)^{1/2}/k^{1/2}}) lower bound on the randomized k-party NOF communication complexity of set disjointness for O(log^{1/3} n) players which is significantly larger than the O(log log n) players allowed in the best previous lower bounds for multiparty set disjointness given by Lee and Shraibman and by Chattopadhyay and Ada (though the bound is not as strong as those previous bounds for o(log log n) players). In addition, we prove lower bounds and separations for read-once AC^0 formulas of smaller depth: a depth 4 function in NP^{cc)_k &#8722; BPP^{cc}_k for k = O(log n/ log log n) and a lower bound of n^{Omega(1/k)}/2^{O(k)} for depth 3 read-once AC^0 formulas.
Thu, 11 Sep 2008 23:29:38 +0300https://eccc.weizmann.ac.il/report/2008/082