Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity

Andris Ambainis, Jānis Iraids, Martins Kokainis

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 fu…