Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR08-082 | 6th May 2010 17:07

Multiparty Communication Complexity and Threshold Circuit Size of AC$^0$

RSS-Feed

Abstract:

We 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.



Changes to previous version:

Improved threshold circuit lower bound (Section 6).


Revision #1 to TR08-082 | 22nd August 2009 21:21

Multiparty Communication Complexity and Threshold Circuit Size of ${\sf AC^0}$





Revision #1
Authors: Paul Beame, Trinh Huynh
Accepted on: 22nd August 2009 21:21
Downloads: 1248
Keywords: 


Abstract:

We 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.


Paper:

TR08-082 | 11th September 2008 00:00

Multiparty Communication Complexity and Threshold Circuit Size of AC^0





TR08-082
Authors: Paul Beame, Trinh Huynh
Publication: 11th September 2008 23:29
Downloads: 1304
Keywords: 


Abstract:

We 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 − 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 − 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.



ISSN 1433-8092 | Imprint