Exact degree
Degree of the unique multilinear real polynomial that represents f exactly.
also written:
Fourier degree, real degree, polynomial degree
Definition
Every $f:\{0,1\}^n\to\mathbb{R}$ has a unique multilinear representation $p(x)=\sum_{S\subseteq[n]}\hat f(S)\prod_{i\in S}x_i$; $\deg(f)=\max\{|S| : \hat f(S)\ne 0\}$. (Equivalently, in the $\pm 1$ Fourier basis, the largest $|S|$ with a nonzero Fourier coefficient.)
Basic facts
- $\deg(f)\le \mathrm{D}(f)$; $\mathrm{D}(f) = O(\deg(f)^3)$ [Midrijanis04].
- $\deg(f) \le \mathrm{s}(f)^2$ [Huang19]; in fact $\deg(f)\le\lambda(f)^2$.
- $\deg(f) = O(\widetilde{\deg}(f)^2)$ [ABKRT21]; tight, e.g. $\mathrm{OR}_n$.
- $\deg(f)\le 2\,\mathrm{Q}_{\mathrm{E}}(f)$; $\deg(f)=n-O(n^{0.548})$ for all non-constant symmetric $f$.
- $\mathrm{bs}(f)\le 2\deg(f)^2$ [Nisan-Szegedy].
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\deg(f)\). “\(\deg(f)\) in terms of it” is the pair with \(\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 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\) | |
| AND total | \(n\) | |
| PARITY total | \(n\) | |
| MAJORITY total | \(n\) | |
| Threshold total | \(n\) putative | The top Fourier coefficient is $\sum_{j\ge k}(-1)^{n-j}\binom{n}{j} = (-1)^{n-k}\binom{n-1}{k-1} \ne 0$, so the multilinear polynomial has the full monomial $x_1\cdots x_n$ for every $1 \le k \le n$. This is the tight end of the von zur Gathen-Roche bound recorded on \(f = f(|x|)\). |
| Symmetric functions (general) total | \(n - O(n^{0.548})\) | What is proved: von zur Gathen--Roche show $\deg(f) \ge n - O(n^{0.548})$ for every non-constant symmetric $f$, and $\deg(f)\le n$ is trivial, so $\deg(f) = n - O(n^{0.548})$. Their exponent comes from prime gaps: $\deg(f) = n - O(g(n))$ where $g$ bounds the gap below $n$, so any improvement on prime gaps improves this line automatically, and the Riemann Hypothesis would give $n - O(\sqrt n\log n)$. Conjecturally the truth is $\deg(f) \in \{n, n-1\}$ for every non-constant symmetric $f$ -- i.e. $\deg(f) = n - O(1)$; it has been checked exhaustively for small $n$, and it holds for every $f$ whose jump structure is a single threshold (see \(\mathrm{THR}^n_k\), where $\deg = n$ exactly). vzGathenRoche97 |
| EXACT-HALF total | \(n\) | |
| ODD-MAX-BIT total | \(n\) putative | Writing $\mathrm{OMB} = \sum_{i \text{ odd}} x_i\prod_{j>i}(1-x_j)$, the monomial $x_1x_2\cdots x_n$ can only come from the $i=1$ term, with coefficient $(-1)^{n-1} \ne 0$. So $\deg = n$ against $\mathrm{sdeg} = 1$ -- the maximum possible separation between exact and sign degree. |
| ADDRESS / multiplexer total | \(k+1\) | |
| Binary tree navigation total | \(k\) putative | Expand recursively: $\mathrm{Nav}_k = (1-x_0)\mathrm{Nav}_{k-1}(L) + x_0\mathrm{Nav}_{k-1}(R)$. The two subtrees have disjoint variable sets, so the top monomial of the right branch times $x_0$ has degree $k$ and cannot be cancelled by anything in the left branch. |
| TRIBES total | \(n\) | The multilinear polynomial $1-\prod_j(1-\prod_{i\in T_j} x_i)$ has the full monomial. |
| AND-OR tree (depth 2) total | \(n^2\) | |
| NAND tree (balanced AND-OR formula) total | \(N\) | True of any read-once formula. |
| Recursive MAJORITY-of-3 total | \(N\) | |
| Kushilevitz's function (iterated) total | \(3^k = N^{0.6131}\) | |
| Rubinstein's function total | \(N = n^2\) putative | Degree is exactly multiplicative under block composition [Tal13], and $\deg(\mathrm{OR}_n) = n$. The gadget has full degree too: $g$ is the sum of $n/2$ point indicators, whose top monomials $y_1\cdots y_n$ all carry the same sign, so they add rather than cancel and $\deg(g) = n$. Hence $\deg = n\cdot n = N$, matching $\mathrm{D}$: this is a full-degree function with $\mathrm{s} = \sqrt N$, i.e. Huang's $\deg \le \mathrm{s}^2$ is tight here as well. Tal13 |
| Ambainis-Sun function total | \((3k+2)^2\) putative | Degree is exactly multiplicative [Tal13]; $\deg(\mathrm{OR}_{3k+2}) = 3k+2$ and $\deg(g) = 3k+2$ (brute force gives $5$ at $k=1$ and $8$ at $k=2$; $g$ is a sum of $2k+1$ mutually exclusive subcube indicators of codimension $3k+2$, and their top monomials cannot all cancel). Note $\deg = \tfrac34 N + O(\sqrt N)$: the function is not of full degree, because each gadget leaves $k$ coordinates free. Tal13 |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2)\) | IJKKKSWW23 |
| Meiburg's tournament-subcube function total | \(\le 7923.9^{\,d}\) putative | $\lambda(f) \ge \sqrt{\deg(f)}$ [ABKRT21], so $\deg \le \lambda^2 \le 89.0162^{2d}$. In the other direction $\mathrm{bs} \le \deg^2$ gives $\deg \ge \sqrt{\mathrm{bs}} \ge 118.3^{\,d}$, so the degree is pinned into $[118.3^{\,d},\, 7923.9^{\,d}]$. Chaining the two is exactly where the $\mathrm{bs} = O(\lambda^4)$ upper bound comes from, and this family shows the truth is at least $\lambda^{2.127}$. ABKRT21 |
| Pointer functions total | \(\widetilde\Omega(n^{1/3})\) | Squeeze: $\mathrm{D}=O(\deg^3)$ [Midrijanis04] against $\mathrm{D}=\widetilde\Omega(n)$. Exact degree cannot follow $\widetilde{\deg}=\widetilde O(n^{1/4})$ down. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | For $\mathrm{BKK}_{\mathrm{CS}}$ [ABK16, Thm 4]. A $1$-input has a unique valid cheat-sheet location $\ell$, so the exact representing polynomial is the plain sum over $\ell$ of the degree-$\widetilde O(\sqrt n)$ polynomials representing "the certificate stored at $\ell$ checks out". ABK16 |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n)\) putative | From $\mathrm{D}=O(\deg^3)$ [Midrijanis04] against $\mathrm{D}=\widetilde\Omega(n^3)$. Huang caps it at $\deg\le\mathrm{s}^2=\widetilde O(n^2)$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n)\) | Summing the indicator polynomials of an unambiguous $1$-DNF represents $g$ exactly, so $\deg\le\mathrm{UC}_1=\widetilde O(n)$; against $\mathrm{C}=\widetilde\Omega(n^2)$ this is [BBGJK21, Cor. 4], improving the classical power-$1.63$ separation of [NW95]. BBGJK21 |
| Gilmer-Saks-Srinivasan functions total | \(\Omega(n^{2/3})\) | Squeeze: $\mathrm{D}=O(\deg^3)$ [Midrijanis04] against $\mathrm{D}=\Theta(n^2)$. The inner $g_n$ is a random indicator, so its degree is almost surely full and the true value is presumably $\Theta(n^2)$; only the lower bound is recorded. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde O(\sqrt n)\) | Summing the indicator polynomials of the leaves of an unambiguous decision tree represents the function exactly, so $\deg\le\mathrm{UC}_1=\widetilde O(\sqrt n)$ [GPW18, Sec. 1.3]. Against $\mathrm{D}=\widetilde\Omega(n)$ this is the record $\mathrm{D}=\widetilde\Omega(\deg^2)$. GPW18 |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | Sum the leaf indicators of the unambiguous decision tree: $\deg\le\mathrm{UC}_1=\widetilde O(n^{1/3})$. Against $\mathrm{R}=\widetilde\Omega(n^{2/3})$ this is the recorded $\mathrm{R}=\widetilde\Omega(\deg^2)$. GJPW18 |
| Ambainis' exact-quantum function total | \(2^d\) | $\deg(\mathrm{NE})=2$ and degree is multiplicative for iterated read-once composition, so $\deg = 2^d = n^{\log_3 2} = n^{0.6309\ldots}$. The gap $\mathrm{D}=\deg^{\log_2 3}$ is what makes an exact quantum speedup possible at all: $\mathrm{Q}_E\ge\deg/2$, so a function with $\mathrm{D}=\Theta(\deg)$ can never show one. NS94 |
| FORRELATION partial | \(O(n)\) | At most $\mathrm{D} = \Theta(n)$. Nothing smaller is known: unlike $\widetilde{\deg} = O(1)$, exact representation cannot exploit the gap between the two promise bands. |
| k-FORRELATION partial | \(O(kn)\) | At most $\mathrm{D} = O(kn)$, against $\widetilde{\deg} = O(k)$: exact representation cannot use the gap between the two promise bands. |
| Simon's problem partial | \(O(n)\) putative | Exponentially below $\mathrm{D}$. Let $z_{i,v}$ be the degree-$n$ conjunction of input bits asserting $g(i) = v$. Then $P = \sum_{i<j}\sum_v z_{i,v}z_{j,v}$ counts colliding pairs, so $P = 0$ on injective tables and $P = 2^{n-1}$ on two-to-one tables, and $2^{1-n}P$ represents $f$ exactly on the promise with degree $2n$ in the input bits. Beware: $P$ is wildly unbounded off the promise, so this does not bound $\widetilde{\deg}$, which is separately $O(n)$ from $2\mathrm{Q}$. |
| Deutsch-Jozsa partial | \(2\) putative | On the promise $f$ is the symmetric function $t \mapsto [t = N/2]$ of $t=|x|$ restricted to $t \in \{0, N/2, N\}$, and $(1 - (1-2t/N)^2)$ interpolates it. Degree $1$ is impossible since $p(0)=p(N)=0$ forces $p \equiv 0$. So $\mathrm{deg} = 2 = 2\,\mathrm{Q}_E$: Deutsch-Jozsa makes $\mathrm{deg} \le 2\mathrm{Q}_E$ tight. |
| Unique search partial | \(1\) putative | $p(x) = \sum_i x_i$ agrees with $f$ at every point of the domain: it is $0$ at $0^n$ and $1$ at each $e_i$. Off the promise it grows to $n$, which the partial-function definition of $\deg$ (agree on $\mathrm{Dom}(f)$, unbounded elsewhere) permits. $f$ is not constant, so $\deg = 1$ exactly. |
| Two-or-none search partial | \(1\) putative | $p(x) = \tfrac12\sum_i x_i$ is $0$ at $0^n$ and $1$ at every weight-$2$ point, so it agrees with $f$ on the whole domain. Off the promise it runs up to $n/2$, which the partial-function definition of $\deg$ permits. |
| Marked bit partial | \(n\) putative | Exactly, and the contrast with \(\mathrm{SEARCH}^{\le 1}_n\) ($\deg = 1$) and \(\mathrm{ApproxIndex}_k\) ($\deg = 2$) is the whole design. Upper: $1 - \prod_b (1-y_b)$. Lower: symmetrise an exact $p$ over the $n$ cells to $q(j_1,j_0)$, of no higher degree, and put $r(t) = q(t,0) - q(0,t)$; then $r(t) = 1$ for every integer $t \in [1,n]$ while $r(0) = 0$, so $r - 1$ has $n$ roots and is not identically zero. Counting the marks cannot work here because their number is not fixed. |
| Dense marked bit partial | \(n/2+1\) putative | Exactly. Upper: $\deg \le \mathrm{D} = n/2+1$. Lower: let $p$ be exact on $\mathrm{Dom}$ and symmetrise over the $n$ cells. Each cell takes one of three values, so Minsky--Papert symmetrisation [MinskyPapert69] gives a polynomial $P(a,c)$ of no higher total degree in the two counts $a = |y|$ and $c = |z|$. The domain says $P(a,0) = 1$ for every integer $a \in [n/2,\, n]$ and $P(0,c) = 0$ for every integer $c \in [n/2,\, n]$ -- that is $n/2+1$ points each. Suppose $\deg p \le n/2$. Then $u(a) := P(a,0)$ is a univariate of degree $\le n/2$ agreeing with the constant $1$ at $n/2+1$ points, so $u \equiv 1$; symmetrically $w(c) := P(0,c) \equiv 0$. But $u(0) = P(0,0) = w(0)$, so $1 = 0$. Hence $\deg p \ge n/2+1$. The contradiction lives at the all-blank array, the one point the promise omits: an exact polynomial has to commit to a value there and cannot commit to two. MinskyPapert69 |
| Gap-Majority partial | \(\Theta(n)\) putative | Exact degree ignores the promise gap entirely. Symmetrising, an exactly representing polynomial gives a univariate $p$ with $p(t) = 0$ for all $\lfloor n/2-\delta n\rfloor + 1$ integers $t \le n/2-\delta n$, so $\deg \ge (1/2-\delta)n$; and $\deg \le \mathrm{D} = \Theta(n)$. Against $\widetilde{\deg} = \Theta(\min(n,1/\delta))$ this is the cleanest $\deg$-vs-$\widetilde{\deg}$ gap there is. |
| Gap-Majority at constant gap partial | \(\Theta(n)\) putative | Exact degree ignores the promise gap: symmetrising an exactly representing polynomial gives a univariate with $\Theta(n)$ forced roots. Against $\widetilde{\deg} = \Theta(1)$ this is the cleanest $\deg$-vs-$\widetilde{\deg}$ gap there is. |
| Parity-labelled FIND-1 partial | \(1\) putative | The linear polynomial $p(x) = (4/n)\sum_{i \text{ odd}} x_i$ is $1$ on every $1$-input and $0$ on every $0$-input of the promise. Off the promise it runs up to $2$, which is allowed for $\deg$ but not for $\widetilde{\deg}$ -- see the settings note at \(\deg(f)\). |
| Approximate index partial | \(\Theta(1)\) putative | At most $2$, and at least $1$ since $f$ is not constant. Count the marked cells instead of finding one: the ball $B(a,r)$ has $V = \sum_{j \le r}\binom kj$ cells whatever the address $a$ is, and on the promise every one of them holds $v$ and no other cell does, so $\tfrac1V\sum_b \mathbb{1}[x_b = 1]$ equals $v$ exactly on the whole domain. Each $\mathbb{1}[x_b=1]$ is a degree-$\le 2$ function of that cell's two encoding bits, so $\deg \le 2$ -- and $\deg = 1$ under the encoding that spends one bit on $\mathbb{1}[x_b=1]$. The address is never looked at. Nothing survives this off the promise, where the sum runs up to $2^k \gg V$: it is unbounded, which is legal for $\deg$ (agree on $\mathrm{Dom}(f)$, unconstrained elsewhere) and is exactly what $\widetilde{\deg}$ forbids. So $\deg = \Theta(1)$ against $\mathrm{D} = \Theta(\sqrt{k\log k})$, and the unbounded polynomial method is worthless here; cf. \(\mathrm{SEARCH}^{\le 1}_n\), where the same collapse happens for the same reason. |
| Collision problem partial | \(\Omega(n^{1/3})\) | $\deg \ge \widetilde{\deg} = \Omega(n^{1/3})$, in the standard encoding of the table by indicator variables $x_{i,v}$. |
| Element distinctness total | \(n\) putative | Encode a symbol $x_i$ by the indicators $x_{i,v}$, one block per position; every function on $\Sigma^n$ is then multilinear of degree $\le n$, via $\sum_x f(x)\prod_i x_{i,x_i}$. For the matching lower bound restrict the domain to $x_i \in \{0, i\}$, where $0$ is a fixed symbol and the $i$ are pairwise distinct: writing $z_i = [x_i = 0]$, the input is all-distinct exactly when at most one $z_i$ is $1$, so $\mathrm{ED}_n$ restricts to $\lnot\mathrm{Th}^n_2$ on a Boolean cube of full dimension. That is a non-constant symmetric function whose univariate interpolant takes the values $1,1,0,\dots,0$, with leading coefficient proportional to $1 - n \ne 0$, hence degree exactly $n$. Restriction cannot raise degree, so $\deg(\mathrm{ED}_n) = n$: on the exact-degree scale there is no speedup at all, in sharp contrast with $\widetilde{\deg} = \Theta(n^{2/3})$. |
| Ambainis-Belovs function partial | \(9\) | Theorem 6, and the whole content of the upper bound. $K(x) = \sum_{a,b,c}\sum_{s,t} \mathbb{1}[x_a{=}s]\,\mathbb{1}[x_b{=}t]\,\mathbb{1}[x_c{=}r_{a,b,c}-s-t]$ has degree $3$ in the indicator variables $\mathbb{1}[x_i = v]$, and $T(z) = \tfrac14 z^3 - \tfrac32 z^2 + \tfrac94 z$ satisfies $T(0)=0$, $T(1)=1$ and $0 \le T \le 1$ on $[0,4]$, so $T(K(x)/n)$ represents $f$ exactly and is bounded on the whole cube. Degree $3 \times 3 = 9$, independent of $n$. AmbainisBelovs23 |
| Surjectivity total | \(n\) putative | Full degree, for every power of two $R \ge 2$ and every even $N \ge R$ -- in particular at $R = N/2$. The coefficient of the top monomial $\prod_i x_i$ is $\pm\sum_x(-1)^{|x|}\mathrm{SURJ}(x)$. Inclusion-exclusion over the missed set gives $\sum_x(-1)^{|x|}\mathrm{SURJ}(x) = (-1)^N\sum_{S\subseteq[R]}(-1)^{|S|}\sigma(S)^N$ with $\sigma(S) = \sum_{v\in S}(-1)^{|v|}$, because $\sum_{v\in[R]}(-1)^{|v|} = 0$. Splitting $S$ by the parity of its elements and passing to exponential generating functions turns this into $N!\,[z^N]\big((1-e^z)(1-e^{-z})\big)^{R/2} = N!\,[z^N]\big(-4\sinh^2(z/2)\big)^{R/2}$, and expanding $\sinh$ leaves $\pm R!\,T(N,R)$, where $T$ is the central factorial number of the second kind. $T(N,R) > 0$ whenever $N \equiv R \bmod 2$ and $N \ge R$, which holds here since $R$ is even. Checked numerically at $R=2,N=4$ (coefficient $-2$) and $R=4,N=8$ (coefficient $504 = 4!\cdot T(8,4)$). |
| Ordered search partial | \(1\) putative | Under the zoo's partial-function convention -- agree with $f$ on the domain, unconstrained off it -- the promise makes $x_j = [\,j \ge k\,]$, so for any target $g(k)$ the degree-one polynomial $p(x) = g(0) + \sum_j (g(j+1)-g(j))(1 - x_j)$ is exactly right. Hence $\deg = 1$ for every Boolean predicate of $k$, and the unbounded polynomial method says nothing here. [BunVoronova23] write "degree $n$" for the same object; they mean a bounded polynomial. |
| Inner product mod 2 total | \(n\) | The multilinear extension is $\tfrac12\big(1 - \prod_{i=1}^{m}(1-2x_iy_i)\big)$, whose leading term $-\tfrac12(-2)^{m}\prod_i x_iy_i$ has degree $2m = n$ and does not cancel. |
| Minsky-Papert one-in-a-box total | \(N = m^3\) | Degree is multiplicative for block composition, and $\deg(\mathrm{AND}_m)\deg(\mathrm{OR}_{m^2}) = m\cdot m^2$. |
| Sink of a tournament total | \(m-1 = \Theta(\sqrt N)\) | Exactly: $\mathrm{SINK}_m = \sum_{v}\prod_{u\ne v}[u\to v]$, a sum of $m$ disjoint monomials of degree $m-1$, and the top-degree terms do not cancel. CMS19 |
| Scorpion graphs total | \(3m-6 = \Theta(\sqrt N)\) putative | Exactly, for $m \ge 5$. For $m \ge 5$ a scorpion has a unique triple $(s,t,b)$ -- the body is the only vertex of degree $m-2$, since a foot misses both $s$ and $t$ -- so $\mathrm{SCORP}_m = \sum_{(s,t,b)} \mathbf{1}[\text{the } 3m-6 \text{ pairs touching } \{s,t,b\} \text{ take their scorpion values}]$ is a sum of disjoint subcube indicators of codimension $3m-6$. Hence $\deg \le 3m-6$. It is attained: all six orderings of one $3$-set share the same touch set $T$ and each contributes $(-1)^{2m-5} = -1$ to the coefficient of $\prod_{e\in T} x_e$, so that coefficient is $-6 \ne 0$. Confirmed exhaustively for $m \le 6$. Note $\deg = \mathrm{s}^1 = \mathrm{C}^1$, all three equal to $3m-6$. |
| Graph connectivity total | \(\binom{m}{2} = N\) putative | Full degree, so connectivity is evasive for the polynomial method too. The coefficient of the top monomial $\prod_e x_e$ in the multilinear extension is $\sum_{S}(-1)^{N-|S|}\mathrm{CONN}(S) = \pm\sum_{S \text{ connected}}(-1)^{|S|}$, and the classical alternating count of connected spanning subgraphs of $K_m$ is $(-1)^{m-1}(m-1)!$ -- never zero. Verified by exact expansion for $m \le 6$, where the top coefficient is $\pm 2, \pm 6, \pm 24, \pm 120$. |
| Ambainis–Iraids–Kokainis unambiguous DNF total | \(O(n)\) | A disjoint DNF equals the sum of its term indicators, each of degree ≤9n. AIK26 |
| Pabbaraju’s optimal unambiguous DNF total | \(O(n)\) | Corollary 1.2: exact representation by the sum of disjoint term indicators. Pabbaraju26 |