Randomized query complexity can beat certificate complexity

Ben-David and Kothari resolve a long-standing open question in query complexity by constructing a total Boolean function f for which bounded-error randomized query complexity R(f) is asymptotically smaller than certificate complexity C(f). They give an explicit f with R(f) = Õ(√C(f)) (the Õ hides polylogarithmic factors), proving a nearly quadratic improvement of randomized query cost over certificate size for total functions. The notation R(f) denotes bounded-error randomized query complexity and C(f) denotes certificate complexity; the construction shows randomized algorithms can certify function values with far fewer queries than the smallest certificate would suggest.

The same construction yields a strong quantum separation as well: bounded-error quantum query complexity Q(f) = Õ(C(f)^{1/4}), which is also nearly optimal up to log factors. Those bounds are essentially tight modulo logarithmic terms, so the work provides near-optimal separations between certificate complexity, randomized query complexity, and quantum query complexity for total Boolean functions. The result overturns prior expectations that certificate complexity tightly controls randomized query cost and supplies an explicit example demonstrating that both randomized and quantum query models can substantially beat certificate-based combinatorial measures.