Let the randomized query complexity of a relation for error probability \epsilon be denoted by \R_\epsilon(\cdot). We prove that for any relation f \subseteq \{0,1\}^n \times \mathcal{R} and Boolean function g:\{0,1\}^m \rightarrow \{0,1\}, \R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g)), where f \circ g^n is the relation obtained by composing f and g. ... more >>>

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized
communication complexity for a ... more >>>

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