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 Ro(f) = O(D(f)07537...). 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 gonn 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 Q E (g) = Õ(√n). These functions show that the relations D(f) = O(R1(f)2) and Ro(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 Ro, 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 Göos, 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.

Additional Metadata
Persistent URL
Grant This work was funded by the European Commission 7th Framework Programme; grant id erc/615307 - Progress in quantum computing: Algorithms, communication, and applications (QPROGRESS)
Ambainis, A, Lee, T. J, Balodis, K. (Kaspars), Santha, M, Belovs, A, & Smotrovs, J. (2016). Separations in query complexity based on pointer functions. doi:10.1145/2897518.2897524