Q The Query Complexity Zoo
\(\deg(f)\)

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.

Other measure \(\deg(f)\) in terms of it It in terms of \(\deg(f)\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total2,2 partial∞ open pair → total1,1 partial∞ open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 open pair → total2,3 partial∞ open pair →
\(\mathrm{s}(f)\) Sensitivity total2,2 partial∞ open pair → total1.63,2 partial∞ open pair →
\(\lambda(f)\) Spectral sensitivity total2,2 partial∞ open pair → total1,1 partial∞ open pair →
\(\mathrm{sdeg}(f)\) Sign degree total∞ partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\deg_2(f)\) Mod-2 degree total∞ derived open pair → total1,1 open pair →

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

Known values

FunctionValueNotes
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