Q The Query Complexity Zoo
\(\widetilde{\deg}_{+}(f)\)

One-sided approximate degree

Approximate degree when the polynomial only has to be large on 1-inputs, not close to 1.

also written: positive one-sided approximate degree, deg_+, one-sided approximation degree

Definition

A real polynomial $p$ is a one-sided approximation to $f : \{0,1\}^n \to \{0,1\}$ if $$|p(x)| \le 1/3 \ \text{ for all } x \in f^{-1}(0), \qquad p(x) \ge 2/3 \ \text{ for all } x \in f^{-1}(1),$$ with no upper bound imposed on the $1$-inputs. $\widetilde{\deg}_+(f)$ is the least degree of such a $p$. Relaxing the constraint on one side only makes this measure asymmetric: $\widetilde{\deg}_+(f)$ and $\widetilde{\deg}_+(\bar f)$ are different quantities, and the conjunction of the two conditions is ordinary approximate degree.

It is the query-complexity shadow of one-sided error: the dual object is a one-sided dual polynomial, which is exactly what the AC$^0$ approximate-degree lower bounds of the last decade construct.

Parameters

\(\varepsilon\) (eps) default \(1/3\)

Basic facts

  • $\mathrm{sdeg}(f) \le \widetilde{\deg}_+(f) \le \widetilde{\deg}(f) \le \deg(f)$: an approximating polynomial is one-sided, and a one-sided one shifted by $1/2$ sign-represents $f$.
  • Both inequalities can be maximally loose, in opposite directions. $\widetilde{\deg}_+(\mathrm{OR}_n) = 1$ (take $p = \sum_i x_i$) while $\widetilde{\deg}(\mathrm{OR}_n) = \Theta(\sqrt n)$; $\mathrm{sdeg}(\mathrm{AND}_n) = 1$ while $\widetilde{\deg}_+(\mathrm{AND}_n) = \Theta(\sqrt n)$.
  • So $\widetilde{\deg}_+$ is not symmetric under negation: $\widetilde{\deg}_+(\mathrm{OR}_n) = 1$ but $\widetilde{\deg}_+(\mathrm{AND}_n) = \Theta(\sqrt n)$, and $\mathrm{AND}_n = \overline{\mathrm{OR}_n(\bar x)}$.
  • $\max\{\widetilde{\deg}_+(f), \widetilde{\deg}_+(\bar f)\}$ is not known to be $\Theta(\widetilde{\deg}(f))$; recovering a two-sided approximation from two one-sided ones loses.
  • Used to prove $\widetilde{\deg}(\mathrm{AC}^0) = \Omega(n^{1-\delta})$ by composing one-sided dual witnesses [Sherstov14onesided, BunThaler17].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\widetilde{\deg}_{+}(f)\). “\(\widetilde{\deg}_{+}(f)\) in terms of it” is the pair with \(\widetilde{\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 \(\widetilde{\deg}_{+}(f)\) in terms of it It in terms of \(\widetilde{\deg}_{+}(f)\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total1,1 partial1,1 open pair → total∞ partial∞ open pair →
\(\mathrm{sdeg}(f)\) Sign degree total∞ partial∞ open pair → total1,1 partial1,1 open pair →
\(\deg(f)\) Exact degree total1,1 partial1,1 open pair → total∞ partial∞ derived open pair →
\(\mathrm{ndeg}(f)\) Nondeterministic degree total1,? partial1,? derived open pair → total2,? partial∞ derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 derived open pair → total∞ partial∞ 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 \(1\) $p(x)=\sum_i x_i$ is $0$ at the unique $0$-input and $\ge 1$ at every $1$-input. The extreme case of one-sided approximation being cheaper than two-sided ($\widetilde{\deg}=\Theta(\sqrt n)$). BT22
AND total \(\Theta(\sqrt n)\) putative Unlike OR, the one-sided relaxation buys nothing: a polynomial bounded by $1/3$ on all of $\{0,1\}^n\setminus\{1^n\}$ and at least $2/3$ at $1^n$ still needs degree $\Omega(\sqrt n)$ by the Markov-brothers argument, and Chebyshev gives $O(\sqrt n)$. NS94 BT22
PARITY total \(n\) Squeezed between $\mathrm{sdeg}=n$ and $\widetilde{\deg}=n$.
MAJORITY total \(\Theta(\sqrt n)\) putative Sharply below $\widetilde{\deg}(\mathrm{MAJ})=\Theta(n)$. A Chebyshev polynomial scaled to be $\le 1/3$ in absolute value on $\{0,\dots,(n-1)/2\}$ has grown past $2/3$ one step later, and nothing constrains it above; the matching $\Omega(\sqrt n)$ is the Markov-brothers bound on an interval with $\Theta(n)$ points.
Threshold total \(\Theta(\sqrt k)\) putative Only the $0$-side is constrained, and it is the interval $\{0,\dots,k-1\}$: Chebyshev on $k$ points gives $O(\sqrt k)$ and Markov gives $\Omega(\sqrt k)$. Compare $\widetilde{\deg} = \Theta(\sqrt{k(n-k+1)})$ -- one-sidedness removes the whole $n-k+1$ factor.
EXACT-HALF total \(\Theta(n)\) putative Equal to $\widetilde{\deg}$, by a normalisation that works because the $1$-inputs form a single slice. Symmetrising a one-sided approximant $p$ gives a univariate $P$ of degree $\le \deg p$ with $|P(k)| \le 1/3$ for $k \ne n/2$ and $M := P(n/2) \ge 2/3$; the one-sided model puts no ceiling on $M$. Now replace $P$ by $P/\max\{1,M\}$. If $M \le 1$ nothing changes and the error at $n/2$ is $1-M \le 1/3$; if $M > 1$ the error at $n/2$ becomes $0$ and the errors elsewhere only shrink. Either way the result is a genuine two-sided $1/3$-approximation, so $\mathrm{odeg} \ge \widetilde{\deg} = \Theta(n)$ [Paturi92]. One-sidedness saves nothing here, in sharp contrast with \(\mathrm{OR}_n\), where $3\sum_i x_i$ gives $\mathrm{odeg} = 1$ against $\widetilde{\deg} = \Theta(\sqrt n)$ -- the difference being that $\mathrm{OR}$ has $1$-inputs on every slice, so no single rescaling can tame them. Paturi92
ODD-MAX-BIT total \(\Theta(\sqrt n)\) putative Upper: $\widetilde{\deg}_+ \le \widetilde{\deg} = \Theta(\sqrt n)$. Lower: one-sided approximate degree does not increase under restriction or under negating variables, and the restriction used on the \(\mathrm{ndeg}(f)\) line turns OMB into an $\mathrm{AND}$ on $\lfloor n/2\rfloor+1$ variables, for which $\widetilde{\deg}_+ = \Theta(\sqrt n)$ (the \(\mathrm{AND}_n\) line). So the one-sided relaxation buys nothing, even though $\mathrm{sdeg}(\mathrm{OMB}) = 1$.
ADDRESS / multiplexer total \(\Theta(k)\) putative Squeezed between $\mathrm{odeg}(\mathrm{PARITY}_k) = k$ -- restrict the table to $y_b = \mathrm{parity}(b)$, as on the \(\mathrm{sdeg}(f)\) line, and note that one-sided approximation survives restriction -- and $\widetilde{\deg}(f) = O(k)$.
Binary tree navigation total \(\Theta(k)\) putative Squeezed between $\mathrm{odeg}(\mathrm{PARITY}_{k-1}) = k-1$ (one-sided approximation also survives the substitution of the \(\widetilde{\deg}_{\varepsilon}(f)\) line) and $\widetilde{\deg}(f) = O(k)$.
TRIBES total \(\Omega(\sqrt{\log n}),\ O(\log n)\) putative Upper: $p(x) = \sum_j \prod_{i \in T_j} x_i$ has degree $w$, equals $0$ on every $0$-input (each tribe has a zero) and is $\ge 1$ on every $1$-input -- a one-sided approximant of degree $w = \Theta(\log n)$, exponentially below $\widetilde{\deg} = \Theta(\sqrt n)$. Lower: restricting all but one tribe to contain a $0$ leaves $\mathrm{AND}_w$, and $\mathrm{odeg}(\mathrm{AND}_w) = \widetilde{\deg}(\mathrm{AND}_w) = \Theta(\sqrt w)$ by the single-slice normalisation argument spelled out on the \(\mathrm{EH}_n\) $\mathrm{odeg}$ line. This is the zoo's cleanest illustration that one-sidedness is worth an exponential factor for a monotone DNF.
AND-OR tree (depth 2) total \(\Omega(\sqrt n),\ O(n)\) Squeezed by $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg}$, whose ends are the recorded $\mathrm{sdeg} = \Omega(\sqrt n)$ and $\widetilde{\deg} = \Theta(n)$.
NAND tree (balanced AND-OR formula) total \(O(\sqrt N)\) One-sided approximate degree is squeezed by $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = \Theta(\sqrt N)$; no lower bound better than the trivial one is known, since the threshold degree of the balanced NAND tree is not pinned down.
Recursive MAJORITY-of-3 total \(O(2^d)\) $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = \Theta(2^d)$. Self-duality of $\mathrm{MAJ}_3$ makes the two one-sided degrees $\widetilde{\deg}_+(f)$ and $\widetilde{\deg}_+(\bar f)$ equal, so no asymmetry can be exploited on this family.
Kushilevitz's function (iterated) total \(O(N^{0.6131})\) $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(N^{0.6131})$; the lower end of the recorded $\widetilde{\deg}$ window, $\Omega(\sqrt N)$, comes from $\mathrm{bs} = O(\widetilde{\deg}^2)$ and does not transfer to the one-sided version.
Rubinstein's function total \(O(\sqrt N)\) $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = \Theta(\sqrt N)$.
Ambainis-Sun function total \(O(N^{3/4})\) $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(N^{3/4})$; the lower end of the recorded $\widetilde{\deg}$ window comes from $\mathrm{bs} = O(\widetilde{\deg}^2)$, which has no one-sided analogue.
AND composed with NOT-EXACT-HALF total \(\widetilde O(n^{3/2})\) $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = \tilde\Theta(n^{3/2})$.
Meiburg's tournament-subcube function total \(\le 7923.9^{\,d}\) putative $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} \le \deg \le 7923.9^{\,d}$ by the \(\deg(f)\) entry.
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $\tilde h_{1,m,m}$: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{1/4})$.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(\sqrt n)$. Like $\widetilde{\deg}$, one-sided approximate degree misses the quantum hardness by a fourth power.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n^{2/3})\) Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{2/3})$, inheriting the caveat on the $\widetilde{\deg}$ line.
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{1/3})$.
Ambainis' exact-quantum function total \(O(2^d)\) Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}\le\deg=2^d$.
FORRELATION partial \(\Theta(1)\) Sandwiched between $\mathrm{sdeg} = \Theta(1)$ and $\widetilde{\deg} = O(1)$.
k-FORRELATION partial \(O(k)\) At most $\widetilde{\deg} = O(k)$.
Simon's problem partial \(O(n)\) At most $\widetilde{\deg} = O(n)$.
Deutsch-Jozsa partial \(2\) Squeezed between $\mathrm{sdeg} = 2$ and $\widetilde{\deg} = 2$.
Gap-Majority partial \(O(\min(n, 1/\delta))\) Between $\mathrm{sdeg} = 1$ and $\widetilde{\deg} = \Theta(\min(n,1/\delta))$. For $\delta \ge 1/8$ a degree-$1$ one-sided approximation exists, so the lower end is attained at constant $\delta$.
Gap-Majority at constant gap partial \(1\) At $\delta \ge 1/8$ a degree-$1$ one-sided approximation exists, so $\mathrm{odeg}$ meets $\mathrm{sdeg}$ at the bottom.
Approximate index partial \(\Theta(1)\) Between $\mathrm{sdeg}$ and $\deg$, both $\Theta(1)$. Like $\deg$ and $\mathrm{sdeg}$, and unlike $\widetilde{\deg}$, one-sided approximate degree never asks the polynomial to stay bounded off the promise.
Collision problem partial \(O(n^{1/3})\) Between $\mathrm{sdeg}$ and $\widetilde{\deg} = O(n^{1/3})$.
Element distinctness total \(O(n^{2/3})\) Between $\mathrm{sdeg}$ and $\widetilde{\deg} = O(n^{2/3})$.
Ambainis-Belovs function partial \(O(1)\) Between $\mathrm{sdeg}$ and $\widetilde{\deg} \le 9$.
Surjectivity total \(\tilde\Omega(\sqrt n),\ \tilde O(n^{3/4})\) $\mathrm{sdeg}\le\widetilde{\deg}_+\le\widetilde{\deg}$ (\(\widetilde{\deg}_{+}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{sdeg}(f)\) vs \(\widetilde{\deg}_{+}(f)\)), and the two ends are the recorded $\mathrm{sdeg}=\tilde\Theta(\sqrt n)$ and $\widetilde{\deg}=\tilde\Theta(n^{3/4})$.
Ordered search partial \(1\) Squeezed between $\mathrm{sdeg} = 1$ and $\deg = 1$. Like $\deg$ and $\mathrm{sdeg}$, and unlike $\widetilde{\deg}$, the one-sided approximate degree is blind to the promise: it never asks the polynomial to stay bounded off the domain.
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{sdeg}(f) \le \widetilde{\deg}_{+}(f) \le \mathrm{D}(f)$, with $\mathrm{sdeg}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m) = \Theta(N^{1/3})\) putative A full $\sqrt m$ below $\widetilde{\deg} = \Theta(m^{3/2})$: dropping the upper constraint on the $1$-inputs is worth a quadratic saving here. Upper: $p(x) = \prod_{j=1}^{m}\big(\sum_{i} x^j_i\big)$ has degree $m$, vanishes whenever some box is empty, and is $\ge 1$ when every box has a $1$ -- exactly a one-sided approximation. Lower: $\mathrm{sdeg}(f) \le \widetilde{\deg}_+(f)$ (\(\mathrm{sdeg}(f)\) vs \(\widetilde{\deg}_{+}(f)\)) and $\mathrm{sdeg} = \Theta(m)$ by [MinskyPapert69]. Note this makes $\mathrm{MP}$ a clean witness that one-sided approximate degree is not $\Theta(\widetilde{\deg})$; compare \(\mathrm{AND}_n\), where the two coincide. MinskyPapert69