Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Juris Smotrovs:

TR15-098 | 15th June 2015
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

Separations in Query Complexity Based on Pointer Functions

Revisions: 2

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})$. ... more >>>

ISSN 1433-8092 | Imprint