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

IEEE Conference on Computational Complexity (CCC)

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness

Paul W. Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

Published Jun 28, 2005• 21 citations
Publisher

Abstract

We prove that corruption, one of the most powerful measures used to analyze 2-party randomized communication complexity, satisfies a strong direct sum property under rectangular distributions. This direct sum bound holds even when the error is allowed to be exponentially close to 1. We use this to analyze the complexity of the widely-studied set disjointness problem in the usual "number-on-the-forehead" (NOF) model of multiparty communication complexity.

DOI
10.1109/ccc.2005.1

Related papers

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

The multiparty communication complexity of set disjointness

Alexander A. Sherstov

We study the set disjointness problem in the number-on-the-forehead model of multiparty communication.

ACM Symposium on Theory of Computing (STOC)•May 19, 2012•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

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 directional derivatives

Alexander A. Sherstov

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.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•18 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
We prove that corruption, one of the most powerful measures used to analyze 2-party randomized communication complexity, satisfies a strong direct sum property under rectangular distributions. This direct sum bound holds even when the error is allowed to be exponentially close to 1. We use this to analyze the complexity of the widely-studied set disjointness problem in the usual "number-on-the-forehead" (NOF) model of multiparty communication complexity.
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 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.
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 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.