Quadratically Tight Relations for Randomized Query Complexity

In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R₀(f): C(f) ≤R₀(f) ≤C(f)². In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R₀(f): EC(f) ≤R₀(f) = O(EC(f)²). For R(f), we prove that EC^2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)² and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R₀(f). The measure is also related to the fractional certificate complexity FC(f) as follows: FC(f) ≤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₀(f), as EC(f) is in fact a relaxation of FC(f). In the second part of the work, we investigate whether the corruption bound corr_𝜖(f) quadratically approximates R(f). By Yao’s theorem, it is enough to prove that the square of the corruption bound upper bounds the distributed query complexity \(\mathsf {D}^{\mu }_{\epsilon }(f)\) for all input distributions μ. Here, we show that this statement holds for input distributions in which the various bits of the input are distributed independently. This is a natural and interesting subclass of distributions, and is also in the spirit of the input distributions studied in communication complexity in which the inputs to the two communicating parties are statistically independent. Our result also improves upon a result of Harsha et al. (2016), who proved a similar weaker statement. We also note that a similar statement in the communication complexity is open.