Randomized query complexity can beat certificate complexity

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.

Computational Complexity (cs.CC); Quantum Physics (quant-ph)

arXiv:2609.15063 [cs.CC]

(or arXiv:2609.15063v1 [cs.CC] for this version)

https://doi.org/10.48550/arXiv.2609.15063 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.