20160619
Separations in query complexity based on pointer functions
Publication
Publication
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zeroerror 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 zeroerror 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 superquadratic gap between its quantum and deterministic query complexities. We also construct a total boolean function gonn variables that has zeroerror randomized query complexity Ω(n/log(n)) and boundederror randomized query complexity R(g) = Õ(√n). This is the first superlinear 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 polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and Ro, a 3/2power separation between Qe and R, and a 4th power separation between approximate degree and boundederror 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 1certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.
Additional Metadata  

dx.doi.org/10.1145/2897518.2897524  
This work was funded by the European Commission 7th Framework Programme; grant id erc/615307  Progress in quantum computing: Algorithms, communication, and applications (QPROGRESS)  
Organisation  Algorithms and Complexity 
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
