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.
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 | \(\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 |