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

ACM Symposium on Theory of Computing (STOC)

Communication lower bounds using directional derivatives

Alexander A. Sherstov

Published May 28, 2013• 18 citations
Publisher

Abstract

We study the set disjointness problem in the most powerful bounded-error model: the number-on-the-forehead model with k parties and arbitrary classical or quantum communication. We obtain a communication lower bound of Omega(√(n)/2k*k) bits, which is essentially optimal. Proving it 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 communication protocols over the reals.

DOI
10.1145/2488608.2488725

Related papers

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

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

Multiparty Communication Complexity of Disjointness

Arkadev Chattopadhyay, Anil Ada

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.

arXiv:0801.3624•Jan 23, 2008•63 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

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
We study the set disjointness problem in the most powerful bounded-error model: the number-on-the-forehead model with k parties and arbitrary classical or quantum communication. We obtain a communication lower bound of Omega(√(n)/2k*k) bits, which is essentially optimal. Proving it 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 communication protocols over the reals.
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.
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 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 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⁰.
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.