For $f:D\subseteq\{0,1\}^n\to\{0,1\}$ and a publicly known $z\in D$, define $f_z^{\mathrm{cert}}$ on $\{z\}\cup f^{-1}(1-f(z))$, accepting $z$ and rejecting the opposite-output inputs. For a complexity measure $M$, put $$M^{\mathrm{cert}}(f)=\max_{z\in D}M(f_z^{\mathrm{cert}}).$$ The input $z$ is free information to the certifying algorithm; only the unknown input is queried. [KLLPV26, Definitions 1–2] systematize this transform.
Collapses onto existing measures. Theorem 3 gives, for partial functions too, $\mathrm{D}^{\mathrm{cert}}=\mathrm{R}_0^{\mathrm{cert}}=\mathrm{UC}^{\mathrm{cert}}=\mathrm{C}$ and $\mathrm{CG}^{\mathrm{cert}}=\Theta(\mathrm{C})$. Bounded-error randomized queries, sabotage, expectational certificates, the partition bound and critical fractional block sensitivity all certify at cost $\Theta(\mathrm{RC})=\Theta(\mathrm{fbs})$. The local measures $\mathrm{C},\mathrm{RC},\mathrm{FC},\mathrm{fbs},\mathrm{bs},\mathrm{s}$ are unchanged by certification (Remark 39).
Theorems 4 and 6 give $$\mathrm{Q}^{\mathrm{cert}}=\Theta(\mathrm{QC})= \Theta(\mathrm{QD}^{\mathrm{cert}})=\Theta(\mathrm{MM}^{\mathrm{cert}})= \Theta(\mathrm{QS}^{\mathrm{cert}})=\Theta(\widetilde{\deg}^{\mathrm{cert}})= \Theta(\mathrm{bm\text{-}deg}^{\mathrm{cert}}).$$ Here QD is quantum distinguishing complexity, MM the positive-weight minimax quantum adversary bound, and bm-deg the whole-cube bounded block-multilinear approximate degree. The QS equality holds for each of the four variants. These are identities after certification, not identities of the original measures. Rational degree is unchanged: $\mathrm{rdeg}^{\mathrm{cert}}=\mathrm{rdeg}$ (Lemma 50). Spectral sensitivity certifies to \(\lambda^{\mathrm{cert}}(f)\), exactly $\sqrt{\mathrm{s}}$ (Theorem 42).
New lower bounds for zero-error quantum queries. Exact and zero-error quantum certification coincide up to constants: $$\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}=\Theta(\mathrm{Q}_0^{\mathrm{cert}})=O(\mathrm{Q}_0).$$ Theorem 5 uses exact amplitude amplification: success probability on the fixed, known reference input can be computed without queries. The zoo records these as \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) and \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\).
The new \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) is the maximum of two degrees of polynomials bounded in $[0,1]$ on the whole cube, each exact on one output class and accurate on the other. It differs from the existing \(\widetilde{\deg}_{+}(f)\), which allows positive-side overshoot. Theorem 8 proves $\overline{\mathrm{osdeg}}=O(\mathrm{Q}_0)$. Its certification transform equals the bounded exact degree certification \(\overline{\deg}^{\mathrm{cert}}(f)\) (Theorem 9). In particular, $$\mathrm{rdeg}\le\overline{\deg}^{\mathrm{cert}}\le\mathrm{C},\qquad \overline{\deg}^{\mathrm{cert}}=O(\overline{\mathrm{osdeg}}),\qquad \overline{\deg}^{\mathrm{cert}}\le2\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}.$$
Boundedness on a promise matters. This paper's exact degree requires $0\le p\le1$ on the whole cube. It equals ordinary \(\deg(f)\) for total functions, but has its own id \(\overline{\deg}(f)\) for partial functions. A certification promise is partial even when the original function is total, so \(\overline{\deg}^{\mathrm{cert}}(f)\) uses \(\overline{\deg}(f)\). Theorem 12 proves $\mathrm{bs}=O((\overline{\deg}^{\mathrm{cert}})^2)$ for partial functions and $\mathrm{C}=O((\overline{\deg}^{\mathrm{cert}})^3)$ for total ones. No application of the total-only upper bound to arbitrary partial functions is recorded.
On AND of complemented EXACT-ONE functions, Theorem 10 and Lemma 55 give $\mathrm{rdeg}=m$, $\mathrm{Q}=\Theta(m)$, $\overline{\deg}^{\mathrm{cert}}=\Omega(m^{3/2}/\log^2m)$, and $\mathrm{Q}_0=O(m^{3/2})$. Thus the new certification lower bounds exceed both rational degree and bounded-error quantum complexity on the same total family. On \(\mathrm{AND}_n \circ \mathrm{OR}_n\), Proposition 52 gives degree $m^2$ against certified degree $m$.