Preprint
Sep 2026
Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
A total Boolean function is constructed whose randomized query complexity with one-sided error satisfies ${R}_1(f) = \Theta(\sqrt{{C}(f)})$, which is optimal even when two-sided error is allowed.
A. Ambainis, Janis Iraids, M. Kokainis
· 0 citations