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)

Rectangles Are Nonnegative Juntas

Mika Göös, Shachar Lovett, Raghu Meka, Thomas W. Watson, David Zuckerman

Published Jun 3, 2015• 38 citations
Publisher

Abstract

We develop a new method to prove communication lower bounds for composed functions of the form f o gn where f is any boolean function on n inputs and g is a sufficiently "hard" two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of f o gn can be simulated by a nonnegative combination of juntas. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only "query" few inputs of f as encoded by the gadget g. Consequently, we characterize the communication complexity of f o gn in all known one-sided zero-communication models by a corresponding query complexity measure of f. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work: We show that SBPcc (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MAcc ≠ SBPcc. These results answer questions of Klauck (CCC 2003) and Bohler et al. (JCSS 2006). We also show that approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. (ICALP) for partial matrices.

DOI
10.1145/2746539.2746596

Related papers

Rectangles Are Nonnegative Juntas

Mika Göös, Shachar Lovett, Raghu Meka +2 more

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$, where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently “hard” two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ g^n$ can be simulated by a nonnegative combination of juntas. This is a new formalization for the intuition that each low-communication randomized protocol can only “query” a few inputs of $f$ as encoded by the gadget $g$. Consequently, we characterize the communication complexity of $f\circ g^n$ in all known one-sided (i.e., not closed under complement) zero-communication models by a corresponding query complexity measure of $f$. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work. We show that $\mathsf{SBP}^{\sf cc}$ (a class characterized by corruption) is not closed under intersection. An immediate corollary is that $\mathsf{MA}^{\sf cc} \neq \mathsf{SBP}^{\sf cc}$. These results answer questions of Klauck [Proceedings of the 18th Conference on Computational Complexity (CCC), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 118--134] and Böhler, Glasser, and Meister [J. Comput. System Sci., 72 (2006), pp. 1043--1076]. We also show that the approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. [Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Springer, Berlin, 2014, pp. 701--712] for partial matrices. In subsequent work, our structure theorem has been applied to resolve the communication complexity of the clique versus independent set problem.

SIAM Journal on Computing•Jan 1, 2016•70 citations

Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays +2 more

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2-O(I)and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem.

arXiv:1204.1505•Annual Symposium on Foundations of Computer Science•Oct 1, 2012•58 citations

Communication Complexity of Set-Disjointness for All Probabilities.

Mika Göös, Thomas W. Watson

We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least α(n) on yes-inputs and at most β(n) on no-inputs, for some functions α(n) > β(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions α and β, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where α = 1/2+ (n) and β = 1/2− (n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a “restricted” class SBP (which lies between MA and AM) and an “unrestricted” class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.

Electronic colloquium on computational complexity•Jan 1, 2014•0 citations

Communication Complexity of Set-Disjointness for All Probabilities

Mika Göös, Thomas W. Watson

We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions alpha and beta, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where alpha=1/2+epsilon(n) and beta=1/2-epsilon(n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a "restricted" class SBP (which lies between MA and AM) and an "unrestricted" class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.

Leibniz international proceedings in informatics•Jan 1, 2014•11 citations

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract

Rahul Jain, Hartmut Klauck, Ashwin Nayak

A basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. We investigate this question in various models of classical communication complexity. We introduce a new measure, the subdistribution bound , which is a relaxation of the well-studied rectangle or corruption bound in communication complexity. We nonetheless show that for the communication complexity of Boolean functions with constant error, the subdistribution bound is the same as the latter measure, up to a constant factor. We prove that the one-way version of this bound tightly captures the one-way public-coin randomized communication complexity of any relation, and the two-way version bounds the two-way public-coin randomized communication complexity from below. More importantly, we show that the bound satisfies the strong direct product property under product distributions for both one- and two-way protocols, and the weak direct product property under arbitrary distributions for two-way protocols. These results subsume and strengthen, in a unified manner, several recent results on the direct product question. The simplicity and broad applicability of our technique is perhaps an indication of its potential to solve yet more challenging questions regarding the direct product problem.

ACM Symposium on Theory of Computing (STOC)•May 17, 2008•36 citations

Randomized Lifting for One-Way Number-on-Forehead Communication

Chenyu Wang

We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed $k\ge2$ and prime $q>2k$, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with $r=O_k(q/\log q)$ such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.

arXiv:2609.32542•Sep 26, 2026•0 citations
We develop a new method to prove communication lower bounds for composed functions of the form f o gn where f is any boolean function on n inputs and g is a sufficiently "hard" two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of f o gn can be simulated by a nonnegative combination of juntas. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only "query" few inputs of f as encoded by the gadget g. Consequently, we characterize the communication complexity of f o gn in all known one-sided zero-communication models by a corresponding query complexity measure of f. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work: We show that SBPcc (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MAcc ≠ SBPcc. These results answer questions of Klauck (CCC 2003) and Bohler et al. (JCSS 2006). We also show that approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. (ICALP) for partial matrices.
We develop a new method to prove communication lower bounds for composed functions of the form f∘gnf\circ g^nf∘gn, where fff is any boolean function on nnn inputs and ggg is a sufficiently “hard” two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of f∘gnf \circ g^nf∘gn can be simulated by a nonnegative combination of juntas. This is a new formalization for the intuition that each low-communication randomized protocol can only “query” a few inputs of fff as encoded by the gadget ggg. Consequently, we characterize the communication complexity of f∘gnf\circ g^nf∘gn in all known one-sided (i.e., not closed under complement) zero-communication models by a corresponding query complexity measure of fff. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work. We show that SBPcc\mathsf{SBP}^{\sf cc}SBPcc (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MAcc≠SBPcc\mathsf{MA}^{\sf cc} \neq \mathsf{SBP}^{\sf cc}MAcc=SBPcc. These results answer questions of Klauck [Proceedings of the 18th Conference on Computational Complexity (CCC), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 118--134] and Böhler, Glasser, and Meister [J. Comput. System Sci., 72 (2006), pp. 1043--1076]. We also show that the approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. [Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Springer, Berlin, 2014, pp. 701--712] for partial matrices. In subsequent work, our structure theorem has been applied to resolve the communication complexity of the clique versus independent set problem.
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2-O(I)and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem.
We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least α(n) on yes-inputs and at most β(n) on no-inputs, for some functions α(n) > β(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions α and β, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where α = 1/2+ (n) and β = 1/2− (n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a “restricted” class SBP (which lies between MA and AM) and an “unrestricted” class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.
We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions alpha and beta, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where alpha=1/2+epsilon(n) and beta=1/2-epsilon(n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a "restricted" class SBP (which lies between MA and AM) and an "unrestricted" class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.
A basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. We investigate this question in various models of classical communication complexity. We introduce a new measure, the subdistribution bound , which is a relaxation of the well-studied rectangle or corruption bound in communication complexity. We nonetheless show that for the communication complexity of Boolean functions with constant error, the subdistribution bound is the same as the latter measure, up to a constant factor. We prove that the one-way version of this bound tightly captures the one-way public-coin randomized communication complexity of any relation, and the two-way version bounds the two-way public-coin randomized communication complexity from below. More importantly, we show that the bound satisfies the strong direct product property under product distributions for both one- and two-way protocols, and the weak direct product property under arbitrary distributions for two-way protocols. These results subsume and strengthen, in a unified manner, several recent results on the direct product question. The simplicity and broad applicability of our technique is perhaps an indication of its potential to solve yet more challenging questions regarding the direct product problem.
We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed k≥2k\ge2k≥2 and prime q>2kq>2kq>2k, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with r=Ok(q/log⁡q)r=O_k(q/\log q)r=Ok​(q/logq) such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.