We show that disjointness requires randomized communication Omega(n^ 1 (k+1) 2^ 2^k ) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound for k >= 3 was log(n) (k-1). Our results give a separation between nondeterministic and randomized multiparty number-on-the-forehead communication complexity for up to k=log log n - O(log log log n) many players. Also by a reduction of Beame, Pitassi, and Segerlind, these results imply subexponential lower bounds on the size of proofs needed to refute certain unsatisfiable CNFs in a broad class of proof systems, including tree-like Lovasz-Schrijver proofs.
Following up on our work, David, Pitassi, and Viola @cite_22 gave an explicit function which separates nondeterministic and randomized communication complexity for up to @math players. They are also able, for any constant @math to give a function computable in @math which separates them for up to @math players. Note that disjointness can be computed in @math , but that our bounds are already trivial for @math players. Even more recently, Beame and Huynh-Ngoc @cite_7 have shown a bound of @math on the @math -party complexity of disjointness. This bound remains non-trivial for up to @math many players, but is not as strong as our bound for few players.
@cite_22 @cite_7
2035762900 2015924804
We exhibit an explicit function f : 0, 1 n → 0, 1 that can be computed by a nondeterministic number-on-forehead protocol communicating O(logn) bits, but that requires nΩ(1) bits of communication for randomized number-on-forehead protocols with k = Δ·logn players, for any fixed Δ We also show that for any k = A ·loglogn the above function f is computable by a small circuit whose depth is constant whenever A is a (possibly large) constant. Recent results again give such functions but only when the number of players is k We prove n (1) lower bounds on the multiparty communication complexity of AC 0 functions in the number-on-forehead (NOF) model for up to �(logn) players. These are the first lower bounds for any AC 0 function for !(loglogn) 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 (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 (1 k) 2 O(k) lower bound on the k-party NOF communication complexity of set disjointness. This is non-trivial for up to �( p logn) players which is significantly larger than the up to �(loglogn) players allowed in the best previous lower bounds for multiparty set disjointness given by Lee and Shraibman [LS08] and Chattopadhyay and Ada [CA08] (though our complexity bounds themselves are not as strong as those in [LS08, CA08] for o(loglogn) players). We derive these results by extending the k-party generalization in [CA08, LS08] of the pattern matrix method of Sherstov [She07, She08]. 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 .