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