Sign degree
Least degree of a polynomial whose sign agrees with f everywhere.
also written:
threshold degree, deg_{\pm}, PP-degree
Definition
The least degree of a real polynomial $p$ that is nonzero on the domain with $\mathrm{sign}(p(x)) = (-1)^{f(x)}$. Equivalently $\mathrm{sdeg}(f) = \lim_{\gamma\to 0}\widetilde{\deg}_{1/2-\gamma}(f)$.
Basic facts
- $\mathrm{sdeg}(f)\le\widetilde{\deg}(f)\le\deg(f)$.
- $\mathrm{sdeg}(\mathrm{ODD\text{-}MAX\text{-}BIT})=1$ while $\widetilde{\deg}=\Omega(n^{?})$: sign degree can be exponentially smaller.
- $\mathrm{sdeg}$ characterises the query analogue of $\mathsf{PP}$ (unbounded-error).
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{sdeg}(f)\). “\(\mathrm{sdeg}(f)\) in terms of it” is the pair with \(\mathrm{sdeg}(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 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(1\) | A linear threshold function: $\sum_i x_i \ge 1$. |
| AND total | \(1\) | $\mathrm{AND}_n = \operatorname{sign}\big(\sum_i x_i - n + \tfrac12\big)$: every halfspace has threshold degree $1$. Against $\widetilde{\deg} = \Theta(\sqrt n)$ and $\deg = n$. |
| PARITY total | \(n\) | MinskyPapert69 |
| MAJORITY total | \(1\) | |
| Threshold total | \(1\) | |
| Symmetric functions (general) total | \(\#\{k \,:\, f_k \ne f_{k+1}\}\) putative | Exactly the number of jumps of the slice pattern. Symmetrizing a sign-representing polynomial keeps it sign-representing, so $\mathrm{sdeg}(f)$ equals the least degree of a univariate $q$ on $\{0,\dots,n\}$ with $\mathrm{sign}\,q(j) = (-1)^{f_j}$; such a $q$ needs a root strictly between each pair of consecutive jumps, and $\prod_i(|x| - a_i)$ with one $a_i$ in each gap attains the bound. Recovers $\mathrm{sdeg}(\mathrm{THR}) = 1$ and $\mathrm{sdeg}(\mathrm{EH}) = 2$. Note this is a display-only value: it is not a function of $n$ and $\Gamma(f)$. |
| EXACT-HALF total | \(2\) | A symmetric function has threshold degree equal to the number of sign changes of its slice pattern, and $\mathrm{EH}$ changes sign twice. Explicitly $p(x) = \tfrac14 - \big(\sum_i x_i - \tfrac n2\big)^2$ is positive exactly on the middle slice. So $\mathrm{sdeg} = 2$ against $\widetilde{\deg} = \Theta(n)$. Threshold degree is not a lower bound on anything interesting on its own: \(\mathrm{MAJ}_n\) does even better with $\mathrm{sdeg} = 1$, and the point of \(\mathrm{MP}_m\) is that a small-depth function can force $\mathrm{sdeg}$ up at all. What makes $\mathrm{EH}$ instructive is that its two sign changes are forced -- one is not enough for a non-monotone slice pattern -- so the exact value is $2$ rather than merely $O(1)$. |
| ODD-MAX-BIT total | \(1\) | It is a linear threshold function -- but every representation needs exponentially large weights. |
| ADDRESS / multiplexer total | \(\Theta(k)\) putative | Restricting the table to $y_b = \mathrm{parity}(b)$ turns $\mathrm{ADDR}_k$ into $\mathrm{PARITY}_k$, and sign degree cannot increase under restriction, so $\mathrm{sdeg} \ge \mathrm{sdeg}(\mathrm{PARITY}_k) = k$; also $\mathrm{sdeg} \le \deg = k+1$. |
| Binary tree navigation total | \(\Theta(k)\) putative | Upper: $2f-1$ sign-represents $f$ and has degree $\deg(f) = k$. Lower: sign-representation survives the substitution of the \(\widetilde{\deg}_{\varepsilon}(f)\) line, so $\mathrm{sdeg}(\mathrm{Nav}_k) \ge \mathrm{sdeg}(\mathrm{PARITY}_{k-1}) = k-1$. Contrast \(\mathrm{OR}_n\) and \(\mathrm{AND}_n\), where $\mathrm{sdeg} = 1$. |
| TRIBES total | \(\Omega(\sqrt{\log n}),\ O(\log n)\) putative | Upper: $\mathrm{sdeg} \le \mathrm{odeg} \le w = \Theta(\log n)$, since a one-sided approximant minus $1/2$ sign-represents. Lower: restrict to $m = \sqrt w$ tribes (force a $0$ into each of the others), leaving $\mathrm{OR}_m \circ \mathrm{AND}_{m^2}$, the negation of the Minsky--Papert function, whose threshold degree is $\Omega(m)$ [MinskyPapert69]. Threshold degree is negation-invariant, so $\mathrm{sdeg}(\mathrm{Tribes}) = \Omega(\sqrt{\log n})$. MinskyPapert69 |
| AND-OR tree (depth 2) total | \(\Omega(\sqrt n) = \Omega(N^{1/4})\) | Minsky-Papert prove $\mathrm{sdeg}(\mathrm{AND}_m \circ \mathrm{OR}_b) = \Omega(\min\{m,\sqrt b\})$, which on the balanced tree ($m = b = n$) is $\Omega(\sqrt n)$. The often-quoted $\Theta(N^{1/3})$ belongs to the unbalanced \(\mathrm{MP}_m\) function $\mathrm{AND}_{m}\circ\mathrm{OR}_{m^2}$, where the two terms of the minimum meet; do not transfer it here. Upper bound here: $\mathrm{sdeg} \le \widetilde{\deg} = \Theta(n)$. MinskyPapert69 |
| NAND tree (balanced AND-OR formula) total | \(O(\sqrt N)\) | From $\mathrm{sdeg} \le \widetilde{\deg} = \Theta(\sqrt N)$. Minsky-Papert-style lower bounds give nothing here: each gate has fan-in $2$, so the $\Omega(\min\{m,\sqrt b\})$ bound for $\mathrm{AND}_m\circ\mathrm{OR}_b$ degenerates to $\Omega(1)$. |
| Recursive MAJORITY-of-3 total | \(O(2^d)\) | From $\mathrm{sdeg} \le \widetilde{\deg} = \Theta(2^d)$. The base gate is a linear threshold function, so $\mathrm{sdeg}(\mathrm{MAJ}_3) = 1$; how fast sign degree grows under self-composition of an LTF is not known, which is why only the upper bound is recorded. |
| Kushilevitz's function (iterated) total | \(O(N^{0.6131})\) | From $\mathrm{sdeg} \le \widetilde{\deg} \le \deg = 3^k$. |
| Rubinstein's function total | \(O(\sqrt N)\) | From $\mathrm{sdeg} \le \widetilde{\deg} = \Theta(\sqrt N)$. |
| Ambainis-Sun function total | \(O(N^{3/4})\) | From $\mathrm{sdeg} \le \widetilde{\deg} = O(N^{3/4})$. |
| AND composed with NOT-EXACT-HALF total | \(\widetilde O(n^{3/2})\) | From $\mathrm{sdeg} \le \widetilde{\deg} = \tilde\Theta(n^{3/2})$. |
| Meiburg's tournament-subcube function total | \(\le 7923.9^{\,d}\) putative | From $\mathrm{sdeg} \le \widetilde{\deg} \le \deg \le 7923.9^{\,d}$. Note the recorded $\widetilde{\deg} = \Omega(118.3^{\,d})$ does not transfer: sign degree can be arbitrarily far below approximate degree. |
| Pointer functions total | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: $\mathrm{sdeg}\le\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{1/4})$. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{sdeg}\le\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(\sqrt n)$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n^{2/3})\) | Squeeze: $\mathrm{sdeg}\le\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: $\mathrm{sdeg}\le\widetilde{\deg}\le\deg$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{sdeg}\le\widetilde{\deg}\le\deg$. |
| Ambainis' exact-quantum function total | \(O(2^d)\) | Squeeze: $\mathrm{sdeg}\le\widetilde{\deg}_+\le\deg=2^d$. |
| FORRELATION partial | \(\Theta(1)\) | Sandwiched: $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(1)$, and at least $1$. Every degree measure below $\widetilde{\deg}$ is constant here while $\mathrm{R} = \widetilde\Theta(\sqrt n)$. |
| k-FORRELATION partial | \(O(k)\) | Sandwiched: $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(k)$. |
| Simon's problem partial | \(O(n)\) | At most $\widetilde{\deg}_+ \le \widetilde{\deg} = O(n)$. |
| Deutsch-Jozsa partial | \(2\) putative | Symmetrising a sign-representing polynomial gives a univariate $q$ on $t \in \{0, N/2, N\}$ with $q(0), q(N) > 0 > q(N/2)$, impossible for degree $1$; and $1 - 2(1-2t/N)^2$ has the right signs. So $\mathrm{sdeg} = \widetilde{\deg} = \deg = 2$ -- no relaxation of degree helps at all. |
| Unique search partial | \(1\) putative | $\tfrac12 - \sum_i x_i$ is positive at $0^n$ and negative at every $e_i$. |
| Two-or-none search partial | \(1\) putative | $1 - \sum_i x_i$ is $+1$ on the $0$-input and $-1$ on every $1$-input. |
| Marked bit partial | \(1\) putative | $\sum_b y_b - \sum_b z_b$ is positive exactly on the $1$-inputs of the domain, since one of the two sums is always $0$ and the other is at least $1$. Against $\widetilde{\deg} = \Theta(\sqrt n)$: sign-representation is free, bounded approximation is not. |
| Dense marked bit partial | \(1\) putative | $\sum_b y_b - \sum_b z_b$ is positive exactly on the $1$-inputs of the domain, since one of the two sums is always $0$ and the other is at least $n/2$. |
| Gap-Majority partial | \(1\) | The single polynomial $p(x) = \sum_i x_i - n/2$ has the right sign at every promise input, whatever $\delta$ is. So $\mathrm{sdeg} = 1$ against $\deg = \Theta(n)$ and $\widetilde{\deg} = \Theta(\min(n,1/\delta))$ -- unbounded-error (the $\mathsf{PP}$ analogue) trivialises gapped majority. |
| Gap-Majority at constant gap partial | \(1\) | $p(x) = \sum_i x_i - n/2$ has the right sign at every promise input. Against $\deg = \Theta(n)$: unbounded error trivialises gapped majority. |
| Parity-labelled FIND-1 partial | \(1\) putative | $\sum_{i \text{ odd}} x_i - 1/2$ has the right sign at every promise input. |
| Approximate index partial | \(\Theta(1)\) | $\mathrm{sdeg} \le \deg = \Theta(1)$: the exact polynomial above, shifted to $\tfrac2V\sum_b \mathbb{1}[x_b=1] - 1$, sign-represents $f$ on the domain. |
| Collision problem partial | \(O(n^{1/3})\) | $\mathrm{sdeg} \le \widetilde{\deg}_{+} \le \widetilde{\deg} = O(n^{1/3})$. |
| Element distinctness total | \(O(n^{2/3})\) | $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(n^{2/3})$. No matching lower bound is recorded: sign degree ignores the size of the approximation error, and the $\Omega(n^{2/3})$ argument does not survive that relaxation. |
| Ambainis-Belovs function partial | \(O(1)\) | $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} \le \deg \le 9$. Everything in the degree column is a constant here; that is the point of the construction. |
| Surjectivity total | \(\tilde\Theta(\sqrt n)\) | [BunThaler21largeerror, Thm. 1.1]: $\deg_{\pm}(\mathrm{SURJ}_{N,R}) = \tilde\Theta(\min\{R,\sqrt N\})$ for $R < N/2$, which at the canonical $R$ is $\tilde\Theta(\sqrt n)$; also [BT22, Thm. 57]. Their Cor. 1.2 turns this into an $\mathrm{AC}^0$ function with unbounded-error communication complexity $\tilde\Omega(\sqrt n)$. BunThaler21largeerror BT22 |
| Ordered search partial | \(1\) | From $\mathrm{sdeg} \le \deg = 1$. |
| Inner product mod 2 total | \(\Theta(n)\) | Restricting $y = 1^m$ leaves $\mathrm{PARITY}_m$, so $\mathrm{sdeg} \ge \mathrm{sdeg}(\mathrm{PARITY}_{n/2}) = n/2$; and $\mathrm{sdeg} \le \deg = n$. |
| Minsky-Papert one-in-a-box total | \(\Theta(m) = \Theta(N^{1/3})\) | The original theorem, and the first threshold-degree lower bound ever proved: no polynomial of degree $o(m)$ sign-represents $\mathrm{MP}_m$. Upper bound $O(m)$: the symmetrisation argument is tight here. MinskyPapert69 |