HackerPapers

arXiv:2609.15063cs.CC

Randomized query complexity can beat certificate complexity

Shalev Ben-David, Robin Kothari

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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.

arXiv comments
6 pages
Journal reference
DOI
Subjects
cs.CCComputational Complexity quant-phQuantum Physics

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Sep 2026 to Sep 2026. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.