Quadratically Tight Relations for Randomized Query Complexity

Abstract

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)\le R_0(f)\le 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)\le C(f)\le 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/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_{\epsilon }^{\mu }(f)$ for product distributions $\mu$ by the square of the query corruption bound (${\mathrm{corr}}_{\epsilon }(f)$) which improves upon a result of Harsha, Jain and Radhakrishnan [2015]. A similar statement for communication complexity is open.

14 pages