Paper Info
Title
Multiparty Communication Complexity and Threshold Circuit Size of AC^0
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 super polynomial 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 are qualitatively optimal, even for formulas of small constant depth. We also exhibit a depth 5 formula in NPc-BPPc for up to Theta(log n) players 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 AC^0 functions.
Year
DOI
Venue
2008
10.1109/FOCS.2009.12
FOCS '09 Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science
Keywords
DocType
ISSN
lower bound,communication complexity
Journal
0272-5428
Citations 
PageRank 
References 
9
0.44
22
Authors
2
Name
Order
Citations
PageRank
Paul Beame12234176.07
Dang-Trinh Huynh-Ngoc2281.69