Separations in Query Complexity Based on Pointer Functions

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.7)(537. )(. .)). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is (Omega) over tilde (n) while its zero-error randomized query complexity is (O) over tilde(root n). We further show that the quantum query complexity of the same function is (O) over tilde (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) = ((O) over tilde root n). This is the first superlinear separation between these two complexity measures. The exact quantum query complexity of the same function is (Q) over tilde (E)(g) = (O) over tilde(root n). These functions show that the relations D(f) = O(R-1(f)(2)) and R-0(f) = (O) over tilde (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 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.