Title: Quadratically Tight Relations for Randomized Query Complexity,
Abstract: Let $f:\{0,1\}^n \rightarrow \{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) \leq 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) \leq 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^\mu_\epsilon(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.