Randomized query complexity can beat certificate complexity
2 days ago
- The paper addresses a longstanding open problem in query complexity, asking whether a total Boolean function exists where randomized query complexity R(f) is significantly less than certificate complexity C(f).
- The authors construct a function where R(f) = O~(sqrt{C(f)}), achieving an optimal separation up to logarithmic factors.
- The same function also yields quantum query complexity Q(f) = O~(C(f)^{1/4}), which is also nearly optimal.