Q The Query Complexity Zoo
\(\overline{\deg}^{\mathrm{cert}}(f)\)

Bounded degree certification complexity

Worst exact bounded degree of a known-input certification promise; a new lower bound on zero-error quantum queries.

also written: degree certification, degcert

Definition

$\overline{\deg}^{\mathrm{cert}}(f)=\max_{z\in D} \overline{\deg}(f_z^{\mathrm{cert}})$, using \(\overline{\deg}(f)\) and the Operational certification complexity promise. Even for a total $f$, this promise is partial, so boundedness on the whole cube is part of the definition. This is the $\deg^{\mathrm{cert}}$ of [KLLPV26].

Basic facts

  • $\mathrm{rdeg}\le\overline{\deg}^{\mathrm{cert}}\le\mathrm{C}$ [KLLPV26, Remark 45 and Lemma 50].
  • $\overline{\deg}^{\mathrm{cert}}=O(\mathrm{Q}_0^{\mathrm{cert}})$ and $O(\mathrm{osdeg})$ [KLLPV26, Theorems 5 and 9, Lemma 48].
  • $\mathrm{bs}=O((\overline{\deg}^{\mathrm{cert}})^2)$ for partial functions, and $\mathrm{C}=O((\overline{\deg}^{\mathrm{cert}})^3)$ for total functions [KLLPV26, Theorem 12].
  • The certification transform of \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) equals $\Theta(\overline{\deg}^{\mathrm{cert}})$ [KLLPV26, Theorem 9].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\overline{\deg}^{\mathrm{cert}}(f)\). “\(\overline{\deg}^{\mathrm{cert}}(f)\) in terms of it” is the pair with \(\overline{\deg}^{\mathrm{cert}}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\overline{\deg}^{\mathrm{cert}}(f)\) in terms of it It in terms of \(\overline{\deg}^{\mathrm{cert}}(f)\)
\(\overline{\deg}(f)\) Exact bounded polynomial degree total1,1 partial1,1 open pair → total2,3 partial2,? derived open pair →
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) One-sided-error bounded polynomial degree total1,1 partial1,1 open pair → total1,3 partial1,? derived open pair →
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) Exact quantum certification complexity total1,1 partial1,1 open pair → total1,3 partial1,? derived open pair →
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) Zero-error quantum certification complexity total1,1 partial1,1 open pair → total1,3 partial1,? derived open pair →
\(\mathrm{rdeg}(f)\) Rational degree total1.5,3 partial∞ open pair → total1,1 partial1,1 open pair →
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 open pair → total2,3 partial2,? open pair →
\(\mathrm{bs}(f)\) Block sensitivity total1,2 partial∞ derived open pair → total1.6309,2 partial1.3333,2 open pair →

The 7 above are this entry’s hand-picked neighbours; the other 86 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
AND total \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
PARITY total \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
MAJORITY total \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
AND-OR tree (depth 2) total \(n\) KLLPV26, Proposition 52: certifying a fixed input reduces to AND or OR on n bits (the family has N=n² inputs). KLLPV26
AND of complemented EXACT-ONE functions total \(\Omega(m^{3/2}/\log^2 m)\) Theorem 10 proof: Ω(√(m³/log⁴m)). KLLPV26