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