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$.

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.

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.