Preprint
Sep 2026
Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
We study how large the certificate complexity ${C}(f)$ of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function $f$ whose randomized query complexity with one-sided error satisfies ${R}_1(f) = \Theta(\sqrt{{C}(f)})$. This separation is optimal e...
A. Ambainis, Janis Iraids, M. Kokainis
· 0 citations