Revision #2 Authors: Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

Accepted on: 26th October 2015 18:17

Downloads: 1619

Keywords:

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\ldots})$. We show this is false by giving an example

of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error

randomized query complexity is $\tilde O(\sqrt{n})$.

We further show that the quantum query complexity of the same function is $\tilde O(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

$\Omega(n/\log(n))$ and bounded-error randomized query complexity $R(g) = \tilde O(\sqrt{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) = \tilde O(\sqrt{n})$.

These two functions show that the relations $D(f) = O(R_1(f)^2)$ and $R_0(f) = \tilde O(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 $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\"{o}\"{o}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.

Improved separation between $Q_E$ and $R_0$.

Revision #1 Authors: Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

Accepted on: 13th July 2015 15:24

Downloads: 1254

Keywords:

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\ldots})$. We show this is false by giving an example

of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error

randomized query complexity is $\tilde O(\sqrt{n})$. This shows that the relations $D(f) \le R_0(f)^2$ and

$D(f) \le 2R_1(f)^2$ are optimal, up to poly-logarithmic factors. We further show that the quantum query complexity of

the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadratic gap between its

quantum and deterministic query complexities.

Variations of this function give new separations between several other query complexity measures, including: the first

super-linear separation between bounded-error and zero-error randomized complexity, larger gaps

between exact quantum query complexity and deterministic/randomized query complexities, and a 4th power separation

between approximate degree and bounded-error randomized complexity.

All of these examples are variants of a function recently introduced by G\"{o}\"{o}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.

Improved separation between R_1 and R_0 and added references to subsequent work.

TR15-098 Authors: Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

Publication: 16th June 2015 13:50

Downloads: 2365

Keywords:

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\ldots})$. We show this is false by giving an example

of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error

randomized query complexity is $\tilde O(\sqrt{n})$. This shows that the relations $D(f) \le R_0(f)^2$ and

$D(f) \le 2R_1(f)^2$ are optimal, up to poly-logarithmic factors. We further show that the quantum query complexity of

the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadratic gap between its

quantum and deterministic query complexities.

Variations of this function give new separations between several other query complexity measures, including: the first

super-linear separation between bounded-error and zero-error randomized complexity, larger gaps

between exact quantum query complexity and deterministic/randomized query complexities, and a 4th power separation

between approximate degree and bounded-error randomized complexity.

All of these examples are variants of a function recently introduced by G\"{o}\"{o}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.