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

Exact bounded polynomial degree

Exact degree with the polynomial also constrained to [0,1] on the entire Boolean cube.

also written: bounded-polynomial degree, Delta_0,0,1

Definition

The minimum degree of a multilinear real polynomial $p$ such that $p(x)=f(x)$ on $D$ and $0\le p(x)\le1$ for every $x\in\{0,1\}^n$. This is $\Delta_{0,0,1}$ of [KLLPV26, Definition 7]. It agrees with \(\deg(f)\) on total functions, but the zoo's \(\deg(f)\) imposes no bound off a partial function's promise. This separate id preserves that distinction.

Basic facts

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\overline{\deg}(f)\). “\(\overline{\deg}(f)\) in terms of it” is the pair with \(\overline{\deg}(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}(f)\) in terms of it It in terms of \(\overline{\deg}(f)\)
\(\deg(f)\) Exact degree total1,1 partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity total2,3 partial2,? derived open pair → total1,1 partial1,1 open pair →
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) One-sided-error bounded polynomial degree total1.32,2 partial1.32,? derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity total1,1 partial1,1 open pair → total2,3 partial1,? derived open pair →
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total2,2 partial∞ derived open pair → total1,1 partial1,1 derived open pair →

The 5 above are this entry’s hand-picked neighbours; the other 88 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