Quadratically Tight Relations for Randomized Query Complexity

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5

Let $f:\{0,1{\}}^n\to \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized que…