Q The Query Complexity Zoo
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\)

One-sided-error bounded polynomial degree

The maximum of the two bounded one-sided-error degrees; lower-bounds zero-error quantum queries.

also written: osdeg, zero-error polynomial lower bound

Definition

$\overline{\mathrm{osdeg}}_\varepsilon(f)= \max\{\overline{\mathrm{osdeg}}^0_\varepsilon(f), \overline{\mathrm{osdeg}}^1_\varepsilon(f)\}$, using \(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\) and \(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\). Both polynomials are bounded in $[0,1]$ on the whole Boolean cube, with one side exact. This differs from \(\widetilde{\deg}_{+}(f)\), where the polynomial may overshoot on positive inputs. Default $\varepsilon=1/3$.

Parameters

\(\varepsilon\) (eps) default \(1/3\)range \((0,1)\)

Basic facts

  • $\widetilde{\deg}=O(\overline{\mathrm{osdeg}})$ and $\overline{\mathrm{osdeg}}\le\overline{\deg}$ [KLLPV26, Fact 46].
  • $\mathrm{rdeg}\le\overline{\mathrm{osdeg}}$ and $\overline{\mathrm{osdeg}}=O(\mathrm{Q}_0)$ [KLLPV26, Corollary 51 and Theorem 8].
  • Its certification transform collapses to \(\overline{\deg}^{\mathrm{cert}}(f)\), while the transform of approximate degree collapses to \(\mathrm{QC}(f)\).

Relations to other measures

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

The 8 above are this entry’s hand-picked neighbours; the other 85 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 of complemented EXACT-ONE functions total \(\Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) degcert=O(osdeg) and osdeg=O(Q₀). KLLPV26