Abstract | ||
---|---|---|
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=2k bits defined by a complete binary tree of NAND gates of depth k, which achieves R0(f) = O(D(f)0.7537…). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Ω(n/log(n)) while its zero-error randomized query complexity is Õ(√n). We further show that the quantum query complexity of the same function is Õ(n1/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 QE(g) = Õ(√n). These functions show that the relations D(f) = O(R1(f)2) and R0(f) = Õ(R(f)2) are optimal, up to poly-logarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R0, a 3/2-power separation between QE 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 Goos, 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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1145/2897518.2897524 | J. ACM |
Keywords | Field | DocType |
Deterministic algorithms,Randomized algorithms,Quantum algorithms,Monte Carlo,Las Vegas | Boolean function,Discrete mathematics,Randomized algorithm,Combinatorics,Clique,Binary tree,Communication complexity,Independent set,Quantum algorithm,NAND logic,Mathematics | Journal |
Volume | Issue | ISSN |
64 | 5 | 0737-8017 |
Citations | PageRank | References |
10 | 0.54 | 16 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andris Ambainis | 1 | 2000 | 183.24 |
Kaspars Balodis | 2 | 17 | 6.03 |
Aleksandrs Belovs | 3 | 131 | 14.50 |
Troy Lee | 4 | 276 | 28.96 |
Miklós Sántha | 5 | 96 | 7.95 |
Juris Smotrovs | 6 | 51 | 7.35 |