Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0801.3624

Multiparty Communication Complexity of Disjointness

Arkadev Chattopadhyay, Anil Ada

Published Jan 23, 2008• 63 citations
arXivHTMLPDF

Abstract

We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.

DOI
10.48550/arxiv.0801.3624

Related papers

Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model

Troy Lee, Adi Shraibman

We show that disjointness requires randomized communication Omega(n1/(k+1)/22k) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound was Omega (log n/k-1). By results of Beame, Pitassi, and Segerlind, this implies 2nOmega(1)lower bounds on the size of tree-like Lovasz-Schrijver proof systems needed to refute certain unsatisfiable CNFs, and super-polynomial lower bounds on the size of a broad class of tree-like proof systems whose terms are degree-d polynomial inequalities for d=log log n-O(log log log n). To prove our bound, we develop a new technique for showing lower bounds in the number-on-the-forehead model which is based on the norm induced by cylinder intersections. This bound naturally extends the linear program bound for rank useful in the two-party case to the case of more than two parties, where the fundamental concept of monochromatic rectangles is replaced by monochromatic cylinder intersections. Previously, the only general method known for showing lower bounds in the unrestricted number-on-the-forehead model was the discrepancy method, which is limited to bounds of size O(log n) for disjointness. To analyze the bound given by our new technique for the disjointness function, we build on an elegant framework developed by Sherstov in the two-party case and Chattopadhyay in the multi-party case which relates polynomial degree to communication complexity. Using this framework we are able to obtain bounds for any tensor of the form F(x1,...,xk)=f(x1Lambda...Lambdaxk) where f is a function which only depends on the number of ones in the input.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•40 citations

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Anup Rao, Amir Yehudayoff

We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4^k). This gives the first lower bound that is linear in n, nearly matching Grolmusz's upper bound of O(log^2(n) + k^2n/2^k). We also simplify the proof of Sherstov's Omega(sqrt(n)/(k2^k)) lower bound for the randomized communication complexity of set disjointness.

Leibniz international proceedings in informatics•Jan 1, 2015•19 citations

Multiparty Communication Complexity of AC 0

Paul W. Beame, Dang-Trinh Huynh-Ngoc

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 Θ(log n) players. These are the first lower bounds for any AC 0 function for ω(log log 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 Ω(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 Θ (√ log n) players which is significantly larger than the up to Θ(log log n) 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(log log n) 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⁰.

Electronic colloquium on computational complexity•Jan 1, 2008•10 citations

Lower Bounds on Quantum Multiparty Communication Complexity

Troy Lee, Gideon Schechtman, Adi Shraibman

A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.

IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•21 citations

Communication Lower Bounds Using Directional Derivatives

Alexander A. Sherstov

We study the set disjointness problem in the most powerful model of bounded-error communication, the k -party randomized number-on-the-forehead model. We show that set disjointness requires Ω(√n/2 k k ) bits of communication, where n is the size of the universe. Our lower bound generalizes to quantum communication, where it is essentially optimal. Proving this bound was a longstanding open problem even in restricted settings, such as one-way classical protocols with k =4 parties [Wigderson 1997]. The proof contributes a novel technique for lower bounds on multiparty communication, based on directional derivatives of protocols over the reals.

Journal of the ACM•Dec 17, 2014•54 citations

Communication Lower Bounds Using Dual Polynomials

Alexander A. Sherstov

Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.

arXiv:0805.2135•Electronic colloquium on computational complexity•May 14, 2008•56 citations
We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.
We show that disjointness requires randomized communication Omega(n1/(k+1)/22k) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound was Omega (log n/k-1). By results of Beame, Pitassi, and Segerlind, this implies 2nOmega(1)lower bounds on the size of tree-like Lovasz-Schrijver proof systems needed to refute certain unsatisfiable CNFs, and super-polynomial lower bounds on the size of a broad class of tree-like proof systems whose terms are degree-d polynomial inequalities for d=log log n-O(log log log n). To prove our bound, we develop a new technique for showing lower bounds in the number-on-the-forehead model which is based on the norm induced by cylinder intersections. This bound naturally extends the linear program bound for rank useful in the two-party case to the case of more than two parties, where the fundamental concept of monochromatic rectangles is replaced by monochromatic cylinder intersections. Previously, the only general method known for showing lower bounds in the unrestricted number-on-the-forehead model was the discrepancy method, which is limited to bounds of size O(log n) for disjointness. To analyze the bound given by our new technique for the disjointness function, we build on an elegant framework developed by Sherstov in the two-party case and Chattopadhyay in the multi-party case which relates polynomial degree to communication complexity. Using this framework we are able to obtain bounds for any tensor of the form F(x1,...,xk)=f(x1Lambda...Lambdaxk) where f is a function which only depends on the number of ones in the input.
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 Θ(log n) players. These are the first lower bounds for any AC 0 function for ω(log log 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 Ω(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 Θ (√ log n) players which is significantly larger than the up to Θ(log log n) 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(log log n) 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⁰.
A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.
We study the set disjointness problem in the most powerful model of bounded-error communication, the k -party randomized number-on-the-forehead model. We show that set disjointness requires Ω(√n/2 k k ) bits of communication, where n is the size of the universe. Our lower bound generalizes to quantum communication, where it is essentially optimal. Proving this bound was a longstanding open problem even in restricted settings, such as one-way classical protocols with k =4 parties [Wigderson 1997]. The proof contributes a novel technique for lower bounds on multiparty communication, based on directional derivatives of protocols over the reals.
Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.