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 #1 to TR08-061 | 1st July 2008 00:00

Multiparty Communication Complexity of AC^0

RSS-Feed




Revision #1
Authors: Paul Beame, Dang-Trinh Huynh-Ngoc
Accepted on: 1st July 2008 00:00
Downloads: 1773
Keywords: 


Abstract:

e prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once AC^0 formulas having k-player randomized multiparty NOF communication complexity n^Omega(1) / 2^O(k). We show similar lower bounds for depth 4 read-once AC^0 formulas that have nondeterministic communication complexity O(log^2 n), yielding exponential separations between k-party nondeterministic and randomized communication complexity for AC^0 functions. As a consequence of the latter bound, we obtain an n^Omega(1/k) / 2^O(k) lower bound on the k-party NOF communication complexity of set disjointness. This is non-trivial for up to Theta(sqrt{log n}) players which is significantly larger than the up to Theta(loglog n) players allowed in the best previous lower bounds for multiparty set disjointness given by Lee and Shraibman [LS08] and by Chattopadhyay and Ada [CA08] (though our complexity bounds themselves are not as strong for o(loglog n) players). We derive these results by extending the k-party generalization in [CA08,LS08] of the pattern matrix method of Sherstov [Sh07,Sh08]. Using this technique, we derive a new sufficient criterion for strong communication complexity lower bounds based on functions having many diverse subfunctions that do not have good low-degree polynomial approximations. This criterion guarantees that such functions have orthogonalizing distributions that are "max-smooth" as opposed to the "min-smooth" orthogonalizing distributions used by Razborov and Sherstov [RS08] to analyze the sign-rank of AC^0.


Paper:

TR08-061 | 11th June 2008 00:00

Multiparty Communication Complexity of AC^0





TR08-061
Authors: Paul Beame, Trinh Huynh
Publication: 12th June 2008 07:18
Downloads: 1333
Keywords: 


Abstract:

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once AC^0 formulas having k-player randomized multiparty NOF communication complexity n^Omega(1) / 2^O(k). We show similar lower bounds for depth 4 read-once AC^0 formulas that have nondeterministic communication complexity O(log^2 n), yielding exponential separations between k-party nondeterministic and randomized communication complexity for AC^0 functions.

As a consequence of the latter bound, we obtain an n^Omega(1/k) / 2^O(k) lower bound on the k-party NOF communication complexity of set disjointness. This is non-trivial for up to Theta(sqrt{log n}) players which is significantly larger than the up to Theta(loglog n) players allowed in the best previous lower bounds for multiparty set disjointness given by Lee and Shraibman [LS08] and by Chattopadhyay and Ada [CA08] (though our complexity bounds themselves are not as strong for o(loglog n) players).

We derive these results by extending the k-party generalization in [CA08,LS08] of the pattern matrix method of Sherstov [Sh07,Sh08]. Using this technique, we derive a new sufficient criterion for strong communication complexity lower bounds based on functions having many diverse subfunctions that do not have good low-degree polynomial approximations. This criterion guarantees that such functions have orthogonalizing distributions that are "max-smooth" as opposed to the "min-smooth" orthogonalizing distributions used by Razborov and Sherstov [RS08] to analyze the sign-rank of AC^0.



ISSN 1433-8092 | Imprint