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:2302.10431

A note on the partition bound for one-way classical communication complexity

Srinivasan Arunachalam, João Fernando Doriguello, Rahul Jain

Published Feb 21, 2023• 0 citations
arXivHTMLPDF

Abstract

We present a linear program for a one-way version of the partition bound of Jain and Klauck, denoted $\mathsf{prt}^1_\varepsilon(f)$, and show that it characterizes the one-way randomized communication complexity $\mathsf{R}_\varepsilon^1(f)$ with shared randomness and worst-case error $\varepsilon$ of any relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. More precisely, for all $\varepsilon,δ\in(0,1/2)$, $\mathsf{R}_\varepsilon^1(f) \geq \log\mathsf{prt}_\varepsilon^1(f)$ and $\mathsf{R}_{\varepsilon+δ}^1(f) \leq \lceil\log\mathsf{prt}_\varepsilon^1(f) + \log\log(1/δ)\rceil$. This improves upon the characterization of $\mathsf{R}_\varepsilon^1(f)$ in terms of the rectangle bound due to Jain, Klauck, and Nayak [STOC'08], which is tight only up to an additive $O(\log(1/δ))$ term.

DOI
10.48550/arxiv.2302.10431

Related papers

A quadratically tight partition bound for classical communication complexity and query complexity

Rahul Jain, Troy Lee, Nisheeth K. Vishnoi

In this work we introduce, both for classical communication complexity and query complexity, a modification of the 'partition bound' introduced by Jain and Klauck [2010]. We call it the 'public-coin partition bound'. We show that (the logarithm to the base two of) its communication complexity and query complexity versions form, for all relations, a quadratically tight lower bound on the public-coin randomized communication complexity and randomized query complexity respectively.

arXiv:1401.4512•Jan 18, 2014•23 citations

Partition Bound Is Quadratically Tight for Product Distributions

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Let f: {0,1}^n*{0,1}^n -> {0,1} be a 2-party function. For every product distribution mu on {0,1}^n*{0,1}^n, we show that CC^{mu}_{0.49}(f) = O(log(prt_{1/8}(f))*log(log(prt_{1/8}(f)))^2), where CC^{mu}_{epsilon}(f) is the distributional communication complexity of f with error at most epsilon under the distribution mu and prt_{1/8}(f) is the partition bound of f, as defined by Jain and Klauck [Proc. 25th CCC, 2010]. We also prove a similar bound in terms of IC_{1/8}(f), the information complexity of f, namely, CC^{mu}_{0.49}(f) = O((IC_{1/8}(f)*log(IC_{1/8}(f)))^2). The latter bound was recently and independently established by Kol [Proc. 48th STOC, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let g: {0,1}^n -> {0,1} be a function. For every bit-wise product distribution mu on {0,1}^n, we show that QC^{mu}_{0.49}(g) = O((log(qprt_{1/8}(g))*log(log(qprt_{1/8}(g))))^2), where QC^{mu}_{epsilon}(g) is the distributional query complexity of f with error at most epsilon under the distribution mu and qprt_{1/8}(g) is the query partition bound of the function g. Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for product distributions.

arXiv:1512.01968•Leibniz international proceedings in informatics•Dec 7, 2015•1 citation

Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity

Rahul Jain

Let f subset of X x Y x Z be a relation. Let the public coin one-way communication complexity of f, with worst case error 1/3, be denoted R^{1,pub}_{1/3}(f). We show that if for computing f^k (k independent copies of f), o(k R^{1,pub}_{1/3}(f)) communication is provided, then the success is exponentially small in k. This settles the strong direct product conjecture for all relations in public coin one-way communication complexity. We show a new tight characterization of public coin one-way communication complexity which strengthens on the tight characterization shown in [J., Klauck, Nayak 08]. We use the new characterization to show our direct product result and this may also be of independent interest.

arXiv:1010.0522•Oct 4, 2010•4 citations

New strong direct product results in communication complexity.

Rahul Jain

We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and e > 0 be a constant. Let R1,pube(f) represent the communication complexity of f, with worst-case error e in this model. We show that if for computing fk (k independent copies of f) in this model, o(k c R1, pub1/3(f)) communication is used, then the success is exponentially small in k. We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest.Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω(n) for the set-disjointness problem on n-bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.

Electronic colloquium on computational complexity•Jan 1, 2011•16 citations

New Strong Direct Product Results in Communication Complexity

Rahul Jain

We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and ϵ > 0 be a constant. Let R 1,pub ϵ ( f ) represent the communication complexity of f , with worst-case error ϵ in this model. We show that if for computing f k ( k independent copies of f ) in this model, o ( k ċ R 1, pub 1/3 ( f )) communication is used, then the success is exponentially small in k . We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest. Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω( n ) for the set-disjointness problem on n -bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.

Journal of the ACM•Jun 30, 2015•22 citations

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

Chengu Wang

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.

cs.CCCross-listedarXiv:2610.30052•Oct 22, 2026•0 citations
We present a linear program for a one-way version of the partition bound of Jain and Klauck, denoted prtε1(f)\mathsf{prt}^1_\varepsilon(f)prtε1​(f), and show that it characterizes the one-way randomized communication complexity Rε1(f)\mathsf{R}_\varepsilon^1(f)Rε1​(f) with shared randomness and worst-case error ε\varepsilonε of any relation f⊆X×Y×Zf\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}f⊆X×Y×Z. More precisely, for all ε,δ∈(0,1/2)\varepsilon,δ\in(0,1/2)ε,δ∈(0,1/2), Rε1(f)≥log⁡prtε1(f)\mathsf{R}_\varepsilon^1(f) \geq \log\mathsf{prt}_\varepsilon^1(f)Rε1​(f)≥logprtε1​(f) and Rε+δ1(f)≤⌈log⁡prtε1(f)+log⁡log⁡(1/δ)⌉\mathsf{R}_{\varepsilon+δ}^1(f) \leq \lceil\log\mathsf{prt}_\varepsilon^1(f) + \log\log(1/δ)\rceilRε+δ1​(f)≤⌈logprtε1​(f)+loglog(1/δ)⌉. This improves upon the characterization of Rε1(f)\mathsf{R}_\varepsilon^1(f)Rε1​(f) in terms of the rectangle bound due to Jain, Klauck, and Nayak [STOC'08], which is tight only up to an additive O(log⁡(1/δ))O(\log(1/δ))O(log(1/δ)) term.
In this work we introduce, both for classical communication complexity and query complexity, a modification of the 'partition bound' introduced by Jain and Klauck [2010]. We call it the 'public-coin partition bound'. We show that (the logarithm to the base two of) its communication complexity and query complexity versions form, for all relations, a quadratically tight lower bound on the public-coin randomized communication complexity and randomized query complexity respectively.
Let f: {0,1}^n*{0,1}^n -> {0,1} be a 2-party function. For every product distribution mu on {0,1}^n*{0,1}^n, we show that CC^{mu}_{0.49}(f) = O(log(prt_{1/8}(f))*log(log(prt_{1/8}(f)))^2), where CC^{mu}_{epsilon}(f) is the distributional communication complexity of f with error at most epsilon under the distribution mu and prt_{1/8}(f) is the partition bound of f, as defined by Jain and Klauck [Proc. 25th CCC, 2010]. We also prove a similar bound in terms of IC_{1/8}(f), the information complexity of f, namely, CC^{mu}_{0.49}(f) = O((IC_{1/8}(f)*log(IC_{1/8}(f)))^2). The latter bound was recently and independently established by Kol [Proc. 48th STOC, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let g: {0,1}^n -> {0,1} be a function. For every bit-wise product distribution mu on {0,1}^n, we show that QC^{mu}_{0.49}(g) = O((log(qprt_{1/8}(g))*log(log(qprt_{1/8}(g))))^2), where QC^{mu}_{epsilon}(g) is the distributional query complexity of f with error at most epsilon under the distribution mu and qprt_{1/8}(g) is the query partition bound of the function g. Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for product distributions.
Let f subset of X x Y x Z be a relation. Let the public coin one-way communication complexity of f, with worst case error 1/3, be denoted R^{1,pub}_{1/3}(f). We show that if for computing f^k (k independent copies of f), o(k R^{1,pub}_{1/3}(f)) communication is provided, then the success is exponentially small in k. This settles the strong direct product conjecture for all relations in public coin one-way communication complexity. We show a new tight characterization of public coin one-way communication complexity which strengthens on the tight characterization shown in [J., Klauck, Nayak 08]. We use the new characterization to show our direct product result and this may also be of independent interest.
We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and e > 0 be a constant. Let R1,pube(f) represent the communication complexity of f, with worst-case error e in this model. We show that if for computing fk (k independent copies of f) in this model, o(k c R1, pub1/3(f)) communication is used, then the success is exponentially small in k. We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest.Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω(n) for the set-disjointness problem on n-bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.
We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and ϵ > 0 be a constant. Let R 1,pub ϵ ( f ) represent the communication complexity of f , with worst-case error ϵ in this model. We show that if for computing f k ( k independent copies of f ) in this model, o ( k ċ R 1, pub 1/3 ( f )) communication is used, then the success is exponentially small in k . We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest. Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω( n ) for the set-disjointness problem on n -bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.
We prove that the randomized communication complexity of Vector-in-Subspace in Rn\mathbb R^nRn with error at most 1/31/31/3 is Θ(n)Θ(\sqrt n)Θ(n​). Alice holds a unit vector uuu and Bob holds an n/2n/2n/2-dimensional subspace HHH; they must distinguish u∈Hu\in Hu∈H from u∈H⊥u\in H^\perpu∈H⊥. An exact one-way quantum protocol uses O(log⁡n)O(\log n)O(logn) qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's O(n)O(\sqrt n)O(n​) upper bound, improves the Ω(n1/3)Ω(n^{1/3})Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n)Ω(\sqrt n)Ω(n​) result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.