Q The Query Complexity Zoo
\(\widetilde{\deg}_{\varepsilon}(f)\)

Approximate degree

Least degree of a polynomial that approximates f pointwise to within eps.

also written: deg~, eps-approximate degree

Definition

$\widetilde{\deg}_\varepsilon(f)$ is the least degree of a real polynomial $p$ with $|p(x)-f(x)|\le\varepsilon$ for all $x\in\mathrm{Dom}(f)$ and (for partial $f$) $|p(x)|\le 1+\varepsilon$ for all $x\in\{0,1\}^n$. Unadorned $\widetilde{\deg}(f):=\widetilde{\deg}_{1/3}(f)$.

Parameters

\(\varepsilon\) (eps) default \(1/3\)range \([0, 1/2)\)

  • Error reduction: $\widetilde{\deg}_{\varepsilon}(f)=O(\widetilde{\deg}_{1/3}(f)\log(1/\varepsilon))$ (compose with an amplifying univariate polynomial).
  • $\varepsilon\to 0$: $\widetilde{\deg}_0(f)=\deg(f)$, and $\deg(f)=O(\widetilde{\deg}(f)^2)$, so the whole range $\varepsilon\in(0,1/3]$ spans at most a quadratic factor for total $f$.
  • Large error / small bias: $\widetilde{\deg}_{1/2-\gamma}(f)$ can be far smaller; at $\gamma\to 0$ it degenerates towards sign degree \(\mathrm{sdeg}(f)\). The "large-error approximate degree" $\widetilde{\deg}_{1/2-1/\mathrm{poly}}$ is its own subject with applications to $\mathsf{PP}$ and to communication complexity.

Detailed records: \(\widetilde{\deg}_{\varepsilon}(f) = O\big(\widetilde{\deg}_{1/3}(f)\log(1/\varepsilon)\big)\) · \(\widetilde{\deg}_{\varepsilon}(f) \text{ as } \varepsilon \to 0 \text{ and } \varepsilon\to 1/2\)

Basic facts

  • $\widetilde{\deg}(f) \le 2\,\mathrm{Q}(f)$: the polynomial method [BBCMdW01].
  • $\mathrm{D}(f) = O(\widetilde{\deg}(f)^4)$ [ABKRT21], improving $O(\widetilde{\deg}^6)$ [BBCMdW01]; matching separation $\mathrm{D}=\tilde\Omega(\widetilde{\deg}^4)$ [ABBLSS17]. Exponent settled at 4.
  • $\mathrm{bs}(f)\le 6\widetilde{\deg}(f)^2$ [Nisan-Szegedy]; $\mathrm{RC}(f)=O(\widetilde{\deg}(f)^2)$ [Kulkarni-Tal].
  • Paturi: for symmetric $f$, $\widetilde{\deg}(f)=\Theta(\sqrt{n(n-\Gamma(f))})$ where $\Gamma(f)=\min\{|2k-n+1| : f_k\ne f_{k+1}\}$.
  • Read-once formulas: $\widetilde{\deg}(f)=\Theta(\sqrt n)$ [ABKRT21, Thm 6].
  • $\lambda(f)=O(\widetilde{\deg}(f))$.
  • For total Boolean $f,g$, $\widetilde{\deg}(f\circ g)=\Theta(\widetilde{\deg}(f)\widetilde{\deg}(g))$: composition holds up to constants [PednekarPodder26composition, Sherstov12robust].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\widetilde{\deg}_{\varepsilon}(f)\). “\(\widetilde{\deg}_{\varepsilon}(f)\) in terms of it” is the pair with \(\widetilde{\deg}_{\varepsilon}(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 \(\widetilde{\deg}_{\varepsilon}(f)\) in terms of it It in terms of \(\widetilde{\deg}_{\varepsilon}(f)\)
\(\deg(f)\) Exact degree total1,1 partial∞ open pair → total2,2 partial∞ open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 open pair → total4,4 partial∞ open pair →
\(\mathrm{sdeg}(f)\) Sign degree total∞ partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree total∞ partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\lambda(f)\) Spectral sensitivity total2,2 partial∞ open pair → total1,1 partial1,2 open pair →
\(\mathrm{C}(f)\) Certificate complexity total2,2 partial∞ open pair → total4,4 partial∞ 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 \(\Theta(\sqrt{n})\) NS94 Paturi92
AND total \(\Theta(\sqrt{n})\)
PARITY total \(n\)
MAJORITY total \(\Theta(n)\) Paturi92
Threshold total \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) Paturi92
Symmetric functions (general) total \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) Paturi92
EXACT-HALF total \(\Theta(n)\) Paturi92
ODD-MAX-BIT total \(\Theta(\sqrt n)\) Squeezed: $\mathrm{bs} = O(\widetilde{\deg}^2)$ gives $\widetilde{\deg} = \Omega(\sqrt n)$, and $\widetilde{\deg} \le 2\mathrm{Q} = O(\sqrt n)$.
ADDRESS / multiplexer total \(\Theta(k)\) Squeezed between $\mathrm{sdeg} = \Omega(k)$ and $\deg = k+1$.
Binary tree navigation total \(\Theta(k)\) putative Substituting one fresh variable $y_j$ for all nodes at level $j$ ($0 \le j \le k-2$), and the constant $\mathrm{parity}(b(v))$ for the bottom node $v$ reached by the path $b(v)$, turns $\mathrm{Nav}_k$ into $\mathrm{PARITY}_{k-1}$ -- the walk reads $y_0,\dots,y_{k-2}$ and then outputs their parity. Approximate degree cannot increase under a substitution of variables by variables and constants, so $\widetilde{\deg}(\mathrm{Nav}_k) \ge \widetilde{\deg}(\mathrm{PARITY}_{k-1}) = k-1$; and $\widetilde{\deg} \le \deg = k$. Navigation is therefore as hard for polynomials as it is for decision trees.
TRIBES total \(\Theta(\sqrt n)\) As for any depth-two AND-OR tree on $n$ variables. BT22
AND-OR tree (depth 2) total \(\Theta(n)\)
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\)
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) Sandwiched: $\lambda(f) = O(\widetilde{\deg}(f))$ (the step [ABKRT21] combine with Huang to get $\deg = O(\widetilde{\deg}^2)$) and $\widetilde{\deg}(f) \le 2\mathrm{Q}(f)$, with $\lambda = 2^d$ and $\mathrm{Q} = \Theta(2^d)$ here. So $\widetilde{\deg}$ sits with $\mathrm{Q}$ and $\lambda$ at $N^{0.63}$, quadratically below $\deg = N$. ABKRT21
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N^{0.6131})\) Not pinned. Upper: $\widetilde{\deg}\le\deg = 3^k$. Lower: $\widetilde{\deg} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(\sqrt N)$. An LP over the $64$ inputs shows the base already has $\widetilde{\deg}(K) = \deg(K) = 3$, but no inner composition theorem for approximate degree is strong enough to iterate that (see comp-adeg).
Rubinstein's function total \(\Theta(\sqrt N) = \Theta(n)\) putative Lower: $\mathrm{bs} \le 6\,\widetilde{\deg}^2$ with $\mathrm{bs} = N/2$. Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(\sqrt N)$. So the quadratic $\deg$-vs-$\widetilde{\deg}$ gap of [ABKRT21] is attained here as well. NS94
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N^{3/4})\) putative Lower: $\mathrm{bs} = O(\widetilde{\deg}^2)$ [NS94] with $\mathrm{bs} = \Theta(N)$. Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(N^{3/4})$. Either way $\widetilde{\deg}$ is strictly below $\deg = \Theta(N)$ unless the gadget's adversary bound is maximal. NS94
AND composed with NOT-EXACT-HALF total \(\tilde\Theta(n^{3/2})\) The gadget has $\widetilde{\deg}(\overline{\mathrm{EH}}_n) = \Theta(n)$ by Paturi's symmetric-function formula $\Theta(\sqrt{n(n-\Gamma)})$ with $\Gamma = 1$ [Paturi92]. Upper: robustification gives $\widetilde{\deg}(f\circ g) = O(\widetilde{\deg}(f)\widetilde{\deg}(g)) = O(\sqrt n\cdot n)$ [Sherstov12robust]. Lower: $\widetilde{\deg}(f\circ g) = \tilde\Omega(\sqrt{\mathrm{bs}(f)}\,\widetilde{\deg}(g)) = \tilde\Omega(\sqrt n\cdot n)$ [CKMPSS23]. So $\widetilde{\deg} = \tilde\Theta(\mathrm{Q})$, and $\deg = \Theta(\widetilde{\deg}^{4/3})$ here. CKMPSS23 Sherstov12robust Paturi92
Meiburg's tournament-subcube function total \(\Omega(118.3^{\,d})\) putative $\mathrm{bs} = O(\widetilde{\deg}^2)$ [NS94], so $\widetilde{\deg} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(14011^{\,d/2})$. Above it sits $\widetilde{\deg} \le \deg \le 7923.9^{\,d}$ from the \(\deg(f)\) entry, so approximate degree is pinned into a factor-$67^{\,d}$ window. NS94
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $\tilde h_{1,m,m}$ [ABBLSS17, Thm 22, Cor. 23]. The approximating polynomial is the sum over the $m$ candidate marked columns of the acceptance polynomials of a $\widetilde O(\sqrt m)$-query column verifier; the sum is legitimate because at most one column can be marked. ABBLSS17
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\widetilde{\deg}\le\deg=\widetilde O(\sqrt n)$, with the floor $\widetilde{\deg}=\widetilde\Omega(\mathrm{D}^{1/4})=\widetilde\Omega(n^{1/4})$ [ABKRT21]. The recorded $\mathrm{Q}=\widetilde\Theta(n)$ is what makes this the $\mathrm{Q}$-vs-$\widetilde{\deg}$ separation.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/4})\) putative From $\mathrm{D}=O(\widetilde{\deg}^4)$ [ABKRT21] against $\mathrm{D}=\widetilde\Omega(n^3)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n^{2/3})\) From the recorded witness $\mathrm{C}=\widetilde\Omega(\widetilde{\deg}^3)$ against $\mathrm{C}=\widetilde\Theta(n^2)$. Matched from below by $\widetilde{\deg}=\Omega(\sqrt{\mathrm{bs}})=\widetilde\Omega(n^{2/3})$, so the value is in fact tight. BBGJK21
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n)\) Squeeze: $\mathrm{bs}=O(\widetilde{\deg}^2)$ [NS94] with $\mathrm{bs}=\Theta(n)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) Squeeze: $\widetilde{\deg}\le\deg=\widetilde O(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) Squeeze: $\widetilde{\deg}\le\deg=\widetilde O(n^{1/3})$. Against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is also $\mathrm{R}=\widetilde\Omega(\widetilde{\deg}^2)$.
Ambainis' exact-quantum function total \(O(2^d)\) Squeeze: $\widetilde{\deg}\le\deg=2^d$, with the floor $\widetilde{\deg}=\Omega(\sqrt{\mathrm{bs}})=\Omega(3^{d/2})$. Since $\widetilde{\deg}(\mathrm{NE})=\deg(\mathrm{NE})=2$ -- a symmetric $3$-bit function that is $0$ exactly at Hamming weights $0$ and $3$ admits no degree-$1$ approximation -- the true value is presumably $\Theta(2^d)$.
FORRELATION partial \(O(1)\) $\widetilde{\deg}\le 2\mathrm{Q} = 2$.
k-FORRELATION partial \(O(k)\) $\widetilde{\deg} \le 2\mathrm{Q} = 2\lceil k/2 \rceil$. Independent of $n$, against $\mathrm{R} = \widetilde\Theta(n^{1-1/k})$.
Simon's problem partial \(O(n)\) $\widetilde{\deg} \le 2\mathrm{Q} = O(n)$, in the indicator variables $\mathbb{1}[g(x) = v]$.
Deutsch-Jozsa partial \(2\) putative Symmetrise: a degree-$1$ univariate with $|q(0)|,|q(N)| \le 1/3$ has $q(N/2) = \tfrac12(q(0)+q(N))$, which cannot reach $2/3$. So approximation does not help either.
Unique search partial \(\Theta(\sqrt n)\) putative Upper: $\widetilde{\deg} \le 2\mathrm{Q}$. Lower: symmetrise an approximating $p$ to a univariate $q$ of the same degree with $q(0) \le 1/3$, $q(1) \ge 2/3$ and $|q(k)| \le 4/3$ at every integer $k \in [0,n]$ -- and this last is exactly where the off-promise boundedness demanded of $\widetilde{\deg}$ is used. Boundedness at the integer points upgrades to boundedness on $[0,n]$ up to a constant factor while $\deg q = O(\sqrt n)$ (Ehlich--Zeller / Coppersmith--Rivlin), and then Markov's inequality $\max|q^{\prime}| \le 2 d^2 \max|q| / n$ against $q(1) - q(0) \ge 1/3$ forces $d = \Omega(\sqrt n)$. NS94 BBCMdW01 Paturi92
Two-or-none search partial \(\Theta(\sqrt n)\) putative Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(\sqrt n)$. Lower: symmetrise to a univariate $q$ of the same degree with $q(0) \le 1/3$, $q(2) \ge 2/3$ and $|q(k)| \le 4/3$ at every integer $k \in [0,n]$ -- the off-promise boundedness is what makes $\widetilde{\deg}$ differ from $\deg$ here. Ehlich--Zeller upgrades that to boundedness on $[0,n]$, and Markov's inequality $\max|q^{\prime}| \le 2d^2\max|q|/n$ against a jump of $1/3$ across an interval of length $2$ gives $d = \Omega(\sqrt n)$. NayakWu99 Paturi92
Marked bit partial \(\Theta(\sqrt n)\) putative The value the function exists for. Upper: $\widetilde{\deg} \le 2\mathrm{Q}$. Lower, by reduction to $\mathrm{OR}$ rather than by symmetrising: let $p$ be $\varepsilon$-approximating and $[0,1]$-valued on the whole cube, and set $P(u) = p(y=u, z=0)$ and $W(u) = p(y=0, z=u)$, both of degree $\le \deg p$. For $u \ne 0^n$ the input $(u,0)$ is a domain $1$-input and $(0,u)$ a domain $0$-input, so $P(u) \ge 1-\varepsilon$ and $W(u) \le \varepsilon$; and $P(0^n) = W(0^n) = p(0,0)$, the all-blank string, whatever that unconstrained value is. So $\Psi = P - W$ has $\Psi(0^n) = 0$, $\Psi(u) \ge 1-2\varepsilon$ off the origin, and $|\Psi| \le 1$ everywhere. So $\Psi$ is a $[-1,1]$-bounded polynomial on the cube separating $0^n$ from the rest by a constant gap ($0$ versus $\ge 1/3$ at $\varepsilon = 1/3$), which is exactly what the Nisan--Szegedy argument rules out below degree $\Omega(\sqrt n)$: symmetrise $\Psi$, and Ehlich--Zeller plus Markov give $\deg p \ge \deg \Psi = \Omega(\sqrt n)$ [NS94]. The cancellation at the origin is the point -- neither $P$ nor $W$ alone is pinned there, but their difference is. NS94 BBCMdW01
Dense marked bit partial \(\Theta(1)\) $\widetilde{\deg} \le 2\mathrm{Q} = \Theta(1)$. Against $\deg = n/2+1$: bounded approximation is free here, exactness is not.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\)· The Nayak-Wu lower bound for approximate counting is a degree bound, so it gives $\widetilde{\deg} = \Omega(\min(n,1/\delta))$; and $\widetilde{\deg} \le 2\mathrm{Q} = O(\min(n,1/\delta))$. NayakWu99
Gap-Majority at constant gap partial \(\Theta(1)\)· $\widetilde{\deg} \le 2\mathrm{Q} = O(1)$, and the Nayak-Wu counting bound is a degree bound. NayakWu99
Parity-labelled FIND-1 partial \(\Theta(1)\) At most $2\mathrm{Q} = O(1)$, and at least $1$. Unlike $\deg$ this is not witnessed by the linear polynomial above, which is unbounded off the promise.
Approximate index partial \(O(\sqrt{k\log k})\) $\widetilde{\deg} \le 2\mathrm{Q} \le 2\mathrm{R} = O(\sqrt{k\log k})$. From below, only $\Omega(1)$, and closing that is a real question rather than an oversight -- note that $\deg = 2$ below is no help, because approximate degree is the one polynomial measure that insists on boundedness off the promise. What a bounded polynomial can do here has a clean reading. Suppose $c_b(a)$, $b \in \{0,1\}^k$, are polynomials in the address of degree $\le d$ with $c_b \ge 0$ and $\sum_b c_b(a) \le 1$ on the whole cube, and $\sum_{b \in B(a,r)} c_b(a) \ge 2/3$ for every $a$ -- a guessing scheme, a distribution over cells of low degree in $a$ that lands in the ball. Then $p(a,x) = \sum_b c_b(a)\big(\mathbb{1}[x_b=1] - \mathbb{1}[x_b=0]\big)$ has degree $d+2$, satisfies $|p| \le 1$ everywhere because the $c_b$ are nonnegative and sum to at most $1$, and equals $(2v-1)\sum_{b \in B(a,r)} c_b(a)$ on the promise; so $\widetilde{\deg} \le d+2$. Two schemes are available and neither beats the algorithm: reading a prefix of $8\sqrt{k\log k}$ address bits and guessing the rest uniformly has degree $8\sqrt{k\log k}$, and biasing every bit by $\gamma = c\sqrt{\log k/k}$ -- the \(\mathrm{noisyR}(f)\) strategy -- gives $c_b(a) = \prod_i (\tfrac12 + \gamma(1-2b_i)(1-2a_i))$, degree $k$, which is worse. Whether some cleverer nonnegative scheme, or a polynomial not of this shape at all, does better is open.
Collision problem partial \(\Theta(n^{1/3})\) The [AaronsonShi04]/[Kutin05] lower bound is a degree bound -- that is what the polynomial method proves -- so $\widetilde{\deg} = \Omega(n^{1/3})$; and $\widetilde{\deg} \le 2\mathrm{Q} = O(n^{1/3})$. Approximate degree is thus the tight measure for the collision problem, where $\mathrm{Adv}$ collapses to $O(1)$. AaronsonShi04 Kutin05
Element distinctness total \(\Theta(n^{2/3})\) Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(n^{2/3})$ by the polynomial method applied to the walk of [Ambainis07]. Lower: the $\Omega(n^{2/3})$ bound of [AaronsonShi04] is a degree bound -- it is proved by symmetrising a low-degree approximating polynomial -- and [Ambainis05smallrange] brings it down to alphabet size $n$. So $\widetilde{\deg}$ is the tight measure here while $\deg = n$. AaronsonShi04 Ambainis05smallrange Ambainis07
Ambainis-Belovs function partial \(O(1)\) At most $\deg \le 9$: an exactly representing polynomial is in particular an approximating one. So the separation below is simultaneously a $\mathrm{Q}$-vs-$\widetilde{\deg}$ separation, and that is the form in which it is usually quoted.
Ben-David-Kundu total search problems relation \(O(\log^7 n)\) Theorem 31: $\widetilde{\deg} = O(t\log^2 n)$, here $O(\log^7 n)$. The witnessing system of polynomials is built from the unbounded degree-$\log(n/2)$ system $p_i(x) = \tfrac{1}{3n}\prod_j x_{ij}$ for $\mathrm{AndOr}_n$, error-reduced to $1/\sqrt n$ at degree $O(\log^2 n)$ and then made bounded by the shift. BenDavidKundu24search
Surjectivity total \(\tilde\Theta(n^{3/4})\) At $R = N/2$. Upper: [Sherstov21, Thm. 1.3] constructs a polynomial of degree $O(\sqrt n\,r^{1/4})$ for $r \le n$; [BKT18, Thm. 3.1] restates it as $\tilde O(N^{3/4})$ for every $R$. Lower: [BKT18, Thm. 4.1], $\tilde\Omega(R^{3/4})$ for some $N = O(R)$. In general $\widetilde{\deg}(\mathrm{SURJ}_{N,R}) = \tilde\Theta(R^{1/4}N^{1/2})$. The $\varepsilon$-dependence is $\tilde\Theta(n^{3/4}\log^{1/4}(1/\varepsilon))$ for $3^{-n} \le \varepsilon \le 1/3$ [SherstovThaler23]. Sherstov21 BKT18 BT22
$k$-distinctness total \(\tilde\Omega\!\big(n^{3/4-1/(4k)}\big),\ O\!\big(n^{3/4-1/(4(2^k-1))}\big)\)· Open, so recorded as a range. Lower: [MTZ20, Thm. 17 / Cor. 18] for $2 \le k \le \log^4 q$ -- the first proof that $4$-distinctness is strictly harder than element distinctness. Upper: [Sherstov21, Thm. 1.1], degree $O(\sqrt n \cdot \min\{n,q\}^{1/2 - 1/(4(1-2^{-k}))})$, and $\tilde O(n^{3/4})$ for all $k \le \mathrm{polylog}(n)$ [MTZ20, Thm. 2]. The 2026 quantum lower bound does not transfer: [BT22] ask exactly how fast $\widetilde{\deg}$ approaches $n^{3/4}$ and it is still open. MTZ20 Sherstov21 BT22
Triangle finding total \(\Omega(m),\ O(m^{5/4})\) Open, and open in exactly the same window as $\mathrm{Q}$. Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(m^{5/4})$ by the polynomial method applied to [CLM20]. Lower: $\widetilde{\deg} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(m)$ by Nisan-Szegedy, which is all that is known -- the Bun-Kothari-Thaler machinery that settled $\widetilde{\deg}$ for \(\mathrm{SURJ}_{N,R}\) and pushed \(\mathrm{DIST}^k_n\) has not been made to say anything here. Exact $\deg$ is left blank on purpose: the top Fourier coefficient $\sum_x(-1)^{|x|}\mathrm{TRI}_m(x)$ is nonzero for $3 \le m \le 7$ -- it is $-1, 3, -4, -3, -61$ -- but it is tiny compared with $2^{\binom m2}$ and nothing rules out its vanishing at larger $m$, so $\deg = \binom m2$ stays a conjecture. CLM20
Recursive Fourier sampling partial \(O(2^{\ell})\) From $\widetilde{\deg}(f) \le 2\,\mathrm{Q}(f)$, which survives the passage to partial functions (\(\widetilde{\deg}_{\varepsilon}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(2^{\ell})$ at $g = g_{\mathrm{mod}3}$. No lower bound is recorded because none is available: with $\mathrm{s} = 0$ and $\mathrm{bs} = 1$ every symmetrisation argument starts from nothing, which is exactly why [Aaronson03rfs] had to invent an adversary proof. Aaronson03rfs
Ordered search partial \(\Omega\!\big(\tfrac{\log n}{(\log\log n)^2}\big),\ O(\log n)\) Decision version. [BunVoronova23, Def. 5, Thm. 12]: $\widetilde{\deg}_{1/2-\gamma}(\mathrm{OS}^{\oplus}_{2^m}) = \Omega(m/\log^2 m - \log(1/\gamma))$, which in the number of input variables $n = 2^m$ is the bound stated. Upper: binary search. Previous best was $\Omega(\sqrt{\log n})$ [BuhrmandeWolf99ordered]. The whole distance between this and $\deg = 1$ is the boundedness requirement off the promise. BunVoronova23
Inner product mod 2 total \(\Theta(n)\) Between $\mathrm{sdeg} = \Omega(n)$ and $\deg = n$.
Minsky-Papert one-in-a-box total \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) The same $\Theta(\sqrt{mb})$ that gives \(\mathrm{AND}_n \circ \mathrm{OR}_n\) its $\Theta(\sqrt N)$; here $\sqrt{m\cdot m^2} = m^{3/2}$.
Sink of a tournament total \(\Omega(\sqrt m),\ O(m)\) Lower: $\widetilde{\deg} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(\sqrt m)$. Upper: $\widetilde{\deg} \le \deg = m-1$. I have not found the exact value stated anywhere; note that pinning it down would also pin $\mathrm{Q}$, which is likewise only known to $\Omega(\sqrt m)$ to $O(m)$.
Scorpion graphs total \(\Omega(\sqrt m),\ O(m)\) Lower: the restriction above turns $\mathrm{SCORP}_m$ into $\mathrm{AND}_{m-3}$, so $\widetilde{\deg} \ge \widetilde{\deg}(\mathrm{AND}_{m-3}) = \Theta(\sqrt m)$. Upper: $\widetilde{\deg} \le \deg = 3m-6$. Not pinned down here; as with \(\mathrm{SINK}_m\), settling it would also settle $\mathrm{Q}$.
Graph connectivity total \(\Omega(m),\ O(m^{3/2})\) Lower: $\mathrm{bs} \le 6\widetilde{\deg}^2$ [NS94] against $\mathrm{bs} = \Theta(m^2)$. Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(m^{3/2})$. The $\Omega(m^{3/2})$ lower bound for \(\mathrm{Q}_{\varepsilon}(f)\) is an adversary bound, not a polynomial one, so the zoo does not know that $\widetilde{\deg}$ matches it.
Ambainis–Iraids–Kokainis certificate cheat sheet total \(O(\sqrt n\log^3 n)\) Approximate degree ≤2Q; an immediate consequence of the quantum algorithm. BBCMdW01 AIK26
Pabbaraju’s quartic approximate-degree function total \(O(\sqrt n\log^{3/2}n)\) Section 5, equation (43); approximate each cell to error 1/(3n²) and sum its polynomial. Pabbaraju26