Q The Query Complexity Zoo
\(\mathrm{sdeg}(f)\)

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.

Other measure \(\mathrm{sdeg}(f)\) in terms of it It in terms of \(\mathrm{sdeg}(f)\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total1,1 partial1,1 derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{rdeg}(f)\) Rational degree total1,1 partial1,1 open pair → total∞ partial∞ derived open pair →
\(\deg(f)\) Exact degree total1,1 partial1,1 open pair → total∞ partial∞ derived open pair →
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree total1,1 partial1,1 open pair → total∞ partial∞ open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
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