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.
The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |