Randomized queries can be far more efficient than certificates
Randomized query complexity can beat certificate complexity
Computational Complexity
Summary
Sometimes, figuring out the answer to a problem can involve checking just a few crucial hints, called certificates, or asking questions randomly. The authors created a special function where randomly asking questions is much faster than relying on certificates alone. This means random strategies can be significantly more efficient at solving some problems. Their method is also nearly the best possible compared to previous approaches.
What this means in practice
- •For algorithm designers: Use the function's insights to design more query-efficient randomized algorithms in scenarios where certificate checks are costly.
- •For quantum computing developers: Inspire the development of quantum query algorithms with improved complexity limits based on the nearly optimal quantum query bounds shown.
A theory result. No direct application yet.
Authors
Shalev Ben-David, Robin Kothari
Abstract
A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.