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

Bounded polynomial degree with error on 0-inputs

A polynomial bounded in [0,1], exact on 1-inputs and approximate on 0-inputs.

Definition

Minimize $\deg p$ subject to $p=1$ on $f^{-1}(1)$, $0\le p\le\varepsilon$ on $f^{-1}(0)$, and $0\le p\le1$ on the whole Boolean cube. This is $\Delta_{\varepsilon,0,1}$ of [KLLPV26, Definition 7]. The superscript names the side on which error is allowed. Default $\varepsilon=1/3$.

Parameters

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

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\). “\(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\) in terms of it” is the pair with \(\overline{\mathrm{osdeg}}^{\,0}_{\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}}^{\,0}_{\varepsilon}(f)\) in terms of it It in terms of \(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\)
\(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) Bounded polynomial degree with error on 1-inputs total2,2 partial2,? derived open pair → total2,2 partial2,? derived open pair →
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) One-sided-error bounded polynomial degree total1,1 partial1,1 open pair → total2,2 partial2,? derived open pair →
\(\overline{\deg}(f)\) Exact bounded polynomial degree total1,1 partial1,1 derived open pair → total2,2 partial2,? derived open pair →
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total2,2 partial2,? derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity total1,1 partial1,1 derived open pair → total2,4 partial2,? 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 \(n\) Exactness on the other 2^n−1 cube inputs forces the degree-n point-indicator polynomial, while the singleton input has a nonzero error gap. KLLPV26
AND total \(\Theta(\sqrt n)\) The Grover acceptance polynomial is exact on the singleton output class; approximate degree gives the matching √n floor. KLLPV26
PARITY total \(\Theta(n)\) Both bounded one-sided polynomials are approximate polynomials, so approximate degree Θ(n) is a floor; exact degree n is a ceiling. KLLPV26
MAJORITY total \(\Theta(n)\) Both bounded one-sided polynomials are approximate polynomials, so approximate degree Θ(n) is a floor; exact degree n is a ceiling. KLLPV26