ECCC-Report TR08-061https://eccc.weizmann.ac.il/report/2008/061Comments and Revisions published for TR08-061en-usTue, 01 Jul 2008 00:00:00 +0300
Revision 1
| Multiparty Communication Complexity of AC^0 |
Paul Beame,
Dang-Trinh Huynh-Ngoc
https://eccc.weizmann.ac.il/report/2008/061#revision1e 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.
Tue, 01 Jul 2008 00:00:00 +0300https://eccc.weizmann.ac.il/report/2008/061#revision1
Paper TR08-061
| Multiparty Communication Complexity of AC^0 |
Paul Beame,
Trinh Huynh
https://eccc.weizmann.ac.il/report/2008/061We 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.
Thu, 12 Jun 2008 07:18:37 +0300https://eccc.weizmann.ac.il/report/2008/061