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:1512.01210 · Electronic colloquium on computational complexity

Nearly optimal separations between communication (or query) complexity and partitions

Robin Kothari

Published Dec 3, 2015• 22 citations
arXivHTMLPDF

Abstract

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and the author. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from lifting the query separation to communication complexity.

DOI
10.48550/arxiv.1512.01210

Related papers

Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions

Andris Ambainis, Martins Kokainis, Robin Kothari

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and Kothari. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from "lifting" the query separation to communication complexity.

Leibniz international proceedings in informatics•Jan 1, 2016•21 citations

Separations in Communication Complexity Using Cheat Sheets and Information Complexity

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5 more

While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2.5 gap. We further present a 1.5 power separation between exact quantum and randomized communication complexity, improving on the previous ≅ 1.15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1.5 separation due to Goos, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.

arXiv:1605.01142•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•14 citations

Separations in Query Complexity Based on Pointer Functions

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3 more

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω( n ) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω( n / log ( n )) and bounded-error randomized query complexity R ( g ) = Õ(√ n ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q E ( g ) = Õ(√ n ). These functions show that the relations D ( f ) = O ( R 1 ( f ) 2 ) and R 0 ( f ) = Õ( R ( f ) 2 ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R 0 , a 3/2-power separation between Q E and R , and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Göös, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

arXiv:1506.04719•Journal of the ACM•Sep 4, 2017•28 citations

Separations in query complexity using cheat sheets

Scott Aaronson, Shalev Ben-David, Robin Kothari

We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity and approximate polynomial degree, showing severe limitations on the power of the polynomial method. Finally, we exhibit a total function with a quadratic gap between quantum query complexity and certificate complexity, which is optimal (up to log factors). These separations are shown using a new, general technique that we call the cheat sheet technique, which builds upon the techniques of Ambainis et al. [STOC 2016]. The technique is based on a generic transformation that converts any (possibly partial) function into a new total function with desirable properties for showing separations. The framework also allows many known separations, including some recent breakthrough results of Ambainis et al. [STOC 2016], to be shown in a unified manner.

arXiv:1511.01937•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•74 citations

Towards better separation between deterministic and randomized query complexity

Sagnik Mukhopadhyay, Swagato Sanyal

We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R0(F)) and randomized one-sided error query complexity (R1(F)): R1(F) = Õ( √ D(F)) and R0(F) = Õ(D(F))3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R0(f) = Ω(D(f))0.753.. This also shows widest separation between R1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous nondeterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R0(f), and polynomial separation between R0(f) and R1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.

•Dec 1, 2015•2 citations

Low-Sensitivity Functions from Unambiguous Certificates

Shalev Ben-David, Pooya Hatami, Avishay Tal

We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.22 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity. We also show that one-sided unambiguous certificate complexity is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between block sensitivity and sensitivity. Along the way, we give a power 1.22 separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power 1.128 separation due to Goos [FOCS 2015]. As a consequence, we obtain an improved lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.

arXiv:1605.07084•Leibniz international proceedings in informatics•May 23, 2016•7 citations
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and the author. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from lifting the query separation to communication complexity.
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and Kothari. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from "lifting" the query separation to communication complexity.
While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2.5 gap. We further present a 1.5 power separation between exact quantum and randomized communication complexity, improving on the previous ≅ 1.15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1.5 separation due to Goos, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω( n ) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω( n / log ( n )) and bounded-error randomized query complexity R ( g ) = Õ(√ n ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q E ( g ) = Õ(√ n ). These functions show that the relations D ( f ) = O ( R 1 ( f ) 2 ) and R 0 ( f ) = Õ( R ( f ) 2 ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R 0 , a 3/2-power separation between Q E and R , and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Göös, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.
We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity and approximate polynomial degree, showing severe limitations on the power of the polynomial method. Finally, we exhibit a total function with a quadratic gap between quantum query complexity and certificate complexity, which is optimal (up to log factors). These separations are shown using a new, general technique that we call the cheat sheet technique, which builds upon the techniques of Ambainis et al. [STOC 2016]. The technique is based on a generic transformation that converts any (possibly partial) function into a new total function with desirable properties for showing separations. The framework also allows many known separations, including some recent breakthrough results of Ambainis et al. [STOC 2016], to be shown in a unified manner.
We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R0(F)) and randomized one-sided error query complexity (R1(F)): R1(F) = Õ( √ D(F)) and R0(F) = Õ(D(F))3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R0(f) = Ω(D(f))0.753.. This also shows widest separation between R1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous nondeterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R0(f), and polynomial separation between R0(f) and R1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.
We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.22 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity. We also show that one-sided unambiguous certificate complexity is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between block sensitivity and sensitivity. Along the way, we give a power 1.22 separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power 1.128 separation due to Goos [FOCS 2015]. As a consequence, we obtain an improved lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.