Quadratically Tight Relations for Randomized Query Complexity

Let $f:\{0,1{\}}^n\to \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is also a quadratically tight bound on $R_0(f)$: $EC(f)\le R_0(f)=O(EC(f{)}^2)$. We prove that $EC(f) \leq C(f) \leq EC(f)^2$ and show that there is a quadratic separation between the two, thus $EC(f)$ gives a tighter upper bound for $R_0(f)$. The measure is also related to the fractional certificate complexity $FC(f)$ as follows: $FC(f)\le EC(f)=O(FC(f{)}^{3\mathrm{/}2})$. This also connects to an open question by Aaronson whether $FC(f)$ is a quadratically tight bound for $R_0(f)$, as $EC(f)$ is in fact a relaxation of $FC(f)$. In the second part of the work, we upper bound the distributed query complexity $D_{ϵ}^{\mu }(f)$ for product distributions $\mu$ by the square of the query corruption bound (${\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}_{ϵ}(f)$) which improves upon a result of Harsha, Jain and Radhakrishnan [2015]. A similar statement for communication complexity is open.