Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions $f$
which counts the number of bits of an input that need to be known in order for the value of the
function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube
where the function is constant. Certificate complexity is well understood for deterministic query (or
decision tree) complexity $(D)$ and other query models such as bounded-error randomized and quantum
complexity $(R, Q)$, but not as well for quantum zero-error $(Q_0)$ and exact query complexity $(Q_E)$,
where there is no agreed-upon certificate “object” (even for $Q$).
Instead, we study an operational notion of certification and apply it to various query-based
models, with a focus on zero-error and exact quantum query complexity, but also on polynomial
degree measures. We give new characterizations of $C, RC$ (randomized certificate complexity) and
QC (quantum certificate complexity), in terms of various measures such as classical and quantum
sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree.
Certification complexity also gives rise to new lower bounds on $Q_E$ and $Q_0$, the quantum analogues
of $D$ and $R_0$, complexity measures for which few lower bound techniques are known which are not
already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean
function for which our certification complexity measure gives a tight lower bound for $Q_0$, but rational
degree and $Q$ are asymptotically smaller.