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

Rational degree

Least d such that f = p/q on the domain with deg(p), deg(q) <= d.

Definition

$\mathrm{rdeg}_\varepsilon(f)$ is the least $\max\{\deg p,\deg q\}$ over rational functions $p/q$ with $|p(x)/q(x) - f(x)|\le\varepsilon$ on $\mathrm{Dom}(f)$; $\mathrm{rdeg}:=\mathrm{rdeg}_0$. No boundedness is required off the domain, which is what makes it behave so differently from $\widetilde{\deg}$.

Characterisation: $\mathrm{rdeg}(f)=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$, hence $\mathrm{rdeg}(f)=\mathrm{rdeg}(\bar f)$ and $\mathrm{rdeg}(f)\le \mathrm{C}(f)$.

Parameters

\(\varepsilon\) (eps) default \(0\)

Basic facts

  • Symmetric $f$: $\mathrm{rdeg}(f)=\Omega(\deg(f))$ (tight).
  • Unate $f$: $\mathrm{rdeg}(f)=\Omega(\sqrt{\deg(f)})$ (tight).
  • Read-once $\mathsf{AC}^0$/$\mathsf{TC}^0$ formulas: $\mathrm{rdeg}(f)=\Omega(\sqrt{\deg(f)})$; with parity gates and depth $d$, $\Omega(\deg(f)^{1/2d})$.
  • Almost every $f$ on $n$ variables has $\mathrm{rdeg}(f)\ge n/2-O(\sqrt n)$.
  • $\deg_{\pm}(f)\le 2\,\mathrm{rdeg}(f)$, tight on parity; and $\mathrm{rdeg}(f)=\Omega(\log n)$ for any $f$ depending on all $n$ variables, tight on \(\mathrm{ADDR}_k\) [KKWY26].
  • Fortnow's question, answered in 2026: $\deg(f)=\widetilde O(\mathrm{rdeg}(f)^3)$ and $\mathrm{D}(f)\le16\,\mathrm{rdeg}(f)^4$ [KKWY26]. The rdeg column of the big matrix read "?" from 1994 until then; what is left is the exponent, see What is the exponent of … versus …?.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{rdeg}(f)\). “\(\mathrm{rdeg}(f)\) in terms of it” is the pair with \(\mathrm{rdeg}(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{rdeg}(f)\) in terms of it It in terms of \(\mathrm{rdeg}(f)\)
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree total∞ partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{ndeg}(f)\) Nondeterministic degree total∞ partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity total∞ partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\deg(f)\) Exact degree total1,1 partial1,? derived open pair → total2,3 partial∞ open pair →
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 open pair → total2,4 partial∞ open pair →
\(\mathrm{sdeg}(f)\) Sign degree total∞ partial∞ derived open pair → total1,1 partial1,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\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\} = \max\{1, n\}$. IJKKKSWW23
AND total \(n\)
PARITY total \(n\)
MAJORITY total \(\Theta(n)\) Symmetric functions have $\mathrm{rdeg} = \Omega(\deg)$. IJKKKSWW23
Threshold total \(\max\{k,\;n-k+1\}\) putative Exactly, from the characterisation $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\} = \max\{k,\,n-k+1\}$ using the \(\mathrm{ndeg}(f)\) line above. Consistent with the two general bounds $\mathrm{rdeg} \le \mathrm{C} = \max\{k,\,n-k+1\}$ and $\mathrm{rdeg} = \Omega(\deg)$ for symmetric $f$ [IJKKKSWW23], which here pin it from both sides. IJKKKSWW23
Symmetric functions (general) total \(\Omega(\deg(f))\) Asymptotically tight: symmetric functions cannot separate rdeg from deg. IJKKKSWW23
EXACT-HALF total \(\Theta(n)\) $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$, and symmetric functions have $\mathrm{rdeg} = \Omega(\deg)$ (see \(f = f(|x|)\)). Since $\mathrm{ndeg}(\overline{\mathrm{EH}}) = 1$, the whole of $\mathrm{rdeg}$ comes from $\mathrm{ndeg}(\mathrm{EH}) = \Theta(n)$ -- this is precisely the $\mathrm{ndeg}$-versus-$\mathrm{rdeg}$ separation that $\mathrm{EH}$ is famous for. IJKKKSWW23
ODD-MAX-BIT total \(\lfloor n/2 \rfloor + 1\) putative Exactly, from $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\ \mathrm{ndeg}(\bar f)\}$. The line above gives $\mathrm{ndeg}(f) = \lfloor n/2\rfloor+1$. For the complement, $\mathrm{ndeg}(\bar f) \le \mathrm{C}^0 = \lceil n/2\rceil$, and setting all even positions to $0$ leaves $\bar f$ equal to the $\mathrm{AND}$ of the negations of the $\lceil n/2 \rceil$ odd variables, so $\mathrm{ndeg}(\bar f) = \lceil n/2\rceil$. The maximum is $\lfloor n/2\rfloor+1$, meeting the general bound $\mathrm{rdeg} \le \mathrm{C}$ recorded on the \(\mathrm{C}(f)\) line. deWolf03
ADDRESS / multiplexer total \(\Theta(k)\) Squeezed: $\mathrm{ndeg}(f) \le \mathrm{rdeg}(f) \le \mathrm{C}(f)$, with $\mathrm{ndeg}(f) = \Theta(k)$ recorded above and $\mathrm{C}(f) = k+1$.
Binary tree navigation total \(\Theta(k)\) $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} = \Theta(k)$ by the \(\mathrm{ndeg}(f)\) line (the complement is another navigation function, with the bottom level flipped), and $\mathrm{rdeg} \le \mathrm{C} = k$.
TRIBES total \(\Theta(n/\log n)\) putative Exactly $s$. From $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$ with $\mathrm{ndeg}(f) = w$ recorded above: $\bar f$ is an AND of ORs, and $\prod_j\big(\sum_{i \in T_j}(1-x_i)\big)$ is nonzero exactly when every tribe contains a $0$, giving $\mathrm{ndeg}(\bar f) \le s$; setting $w-1$ bits of each tribe to $1$ restricts $\bar f$ to $\mathrm{AND}_s$, whose nondeterministic degree is $s$, giving the match. So $\mathrm{rdeg} = \Theta(n/\log n)$ against $\deg = n$ -- a genuine, if only logarithmic, rational-vs-exact degree gap on a monotone function.
AND-OR tree (depth 2) total \(n\) $\mathrm{ndeg}(f) = n\cdot\mathrm{ndeg}(\mathrm{OR}_n) = n$ and $\mathrm{ndeg}(\bar f)=\mathrm{ndeg}(\mathrm{NOR}_n)=n$. IJKKKSWW23
NAND tree (balanced AND-OR formula) total \(2^{\lceil d/2\rceil} = \Theta(\sqrt N)\) putative $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$ [IJKKKSWW23], and the recursion in the \(\mathrm{ndeg}(f)\) entry gives $\mathrm{ndeg}(\overline{f_d}) = 2\,\mathrm{ndeg}(f_{d-1}) = 2^{\lceil d/2\rceil}$, which is the larger of the two. So exact rational degree equals $\mathrm{C}^0$ here, and $\mathrm{rdeg} = \Theta(\sqrt{\deg})$ -- the extremal behaviour for read-once formulas. IJKKKSWW23
Recursive MAJORITY-of-3 total \(\Omega(1.732^{\,d}),\ O(2^d)\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \mathrm{C}(f) = 2^d$ [IJKKKSWW23]. From below, read-once $\mathsf{AC}^0/\mathsf{TC}^0$ formulas satisfy $\mathrm{rdeg} = \Omega(\sqrt{\deg})$, i.e. $\Omega(3^{d/2}) = \Omega(1.732^{\,d})$ here. The remaining factor-$1.155^{\,d}$ window is an instance of the open question of whether $\mathrm{rdeg} = \deg^{\Omega(1)}$ is tight for read-once formulas. IJKKKSWW23
Kushilevitz's function (iterated) total \(\le 3^k = N^{0.6131}\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \deg(f) = 3^k$, since $\deg(\bar f) = \deg(f)$. Again far below $\mathrm{C} = N$. IJKKKSWW23
Rubinstein's function total \(\le N/2\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$ [IJKKKSWW23]; the first term is $\le n$ by the \(\mathrm{ndeg}(f)\) entry, and the second is $\le \mathrm{C}^0 = N/2$. The $0$-side dominates, so exact rational degree cannot be pushed below $\mathrm{C}^0$ by this argument. IJKKKSWW23
Ambainis-Sun function total \(\le 6k^2+7k+2\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \mathrm{C} = 6k^2+7k+2$ [IJKKKSWW23]; the $0$-side, with $\mathrm{C}^0 = 6k^2+7k+2$, is what dominates. IJKKKSWW23
AND composed with NOT-EXACT-HALF total \(\Theta(n) = \Theta(\sqrt N)\) $\mathrm{ndeg}(f) = n \cdot \mathrm{ndeg}(\overline{\mathrm{EH}}_n) = n$ and $\mathrm{ndeg}(\bar f) = \mathrm{ndeg}(\mathrm{EH}_n) \le n$. IJKKKSWW23
Meiburg's tournament-subcube function total \(\le 7923.9^{\,d}\) putative $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \deg(f)$ [IJKKKSWW23], since $\deg(\bar f) = \deg(f)$, and $\deg \le 7923.9^{\,d}$. IJKKKSWW23
Pointer functions total \(\widetilde O(\sqrt n)\) Variant $f_{2m,m}$: $\mathrm{rdeg}\le\mathrm{C}=\widetilde O(\sqrt n)$ -- write the exact rational representation from the certificate cover.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{rdeg}\le\mathrm{C}=\widetilde O(\sqrt n)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n)\) Squeeze: $\mathrm{rdeg}=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}\le\deg=\widetilde O(n)$. Against $\mathrm{C}=\widetilde\Theta(n^2)$ this inherits the $\mathrm{C}$-vs-$\deg$ quadratic gap.
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{rdeg}\le\deg=\widetilde O(\sqrt n)$ (take the denominator $q\equiv 1$). Against $\mathrm{D}=\widetilde\Theta(n)$ this is a quadratic $\mathrm{D}$-vs-$\mathrm{rdeg}$ gap.
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) Squeeze: $\mathrm{rdeg}\le\deg=\widetilde O(n^{1/3})$ (take the denominator $q\equiv 1$). Against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is a quadratic $\mathrm{R}$-vs-$\mathrm{rdeg}$ gap.
Ambainis' exact-quantum function total \(O(2^d)\) Squeeze: $\mathrm{rdeg}\le\deg=2^d$ (take the denominator $q\equiv 1$).
FORRELATION partial \(O(n)\) At most $\mathrm{C} = \Theta(n)$.
k-FORRELATION partial \(O(kn)\) At most $\mathrm{C} = O(kn)$; from below $\mathrm{rdeg} \ge \widetilde{\mathrm{rdeg}} \ge 1$.
Simon's problem partial \(O(2^{n/2})\) At most $\mathrm{C} = \Theta(2^{n/2})$; from below $\mathrm{rdeg} \ge \mathrm{ndeg} = \Theta(1)$.
Deutsch-Jozsa partial \(1\) putative Rational degree collapses below exact degree. By the characterisation $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$: $\mathrm{ndeg}(f) = 1$ (see below), and $\mathrm{ndeg}(\bar f) = 1$ too, since $p(x) = |x| - N/2$ vanishes on exactly the balanced inputs. So $\mathrm{rdeg} = 1 < \deg = \widetilde{\deg} = \mathrm{sdeg} = 2$.
Unique search partial \(1\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$, and $1 - \sum_i x_i$ vanishes exactly on the $1$-inputs, so both halves are $1$.
Two-or-none search partial \(1\) Both halves are degree $1$: $\sum_i x_i$ vanishes exactly on the $0$-input, and $2 - \sum_i x_i$ exactly on the $1$-inputs.
Marked bit partial \(1\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$, and $\sum_b z_b$ does for $\bar f$ what $\sum_b y_b$ does for $f$.
Dense marked bit partial \(1\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$, and $\sum_b z_b$ does for $\bar f$ what $\sum_b y_b$ does for $f$.
Gap-Majority partial \(\Theta(n)\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\} = \Theta(n)$, the two sides being symmetric. Exact rational approximation is therefore as hard as exact polynomial representation here, even though $\mathrm{rdeg}_{\varepsilon} = O(\min(n,1/\delta))$.
Gap-Majority at constant gap partial \(\Theta(n)\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$, the two sides being symmetric. Against $\mathrm{rdeg}_\varepsilon = \Theta(1)$ and $\mathrm{Q} = \Theta(1)$: on partial functions rational degree is unbounded in terms of everything bounded-error, which is why What is the exponent of … versus …? is a total-function question.
Parity-labelled FIND-1 partial \(1\) putative $\max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$, and the complement is handled by $\sum_{i \text{ even}} x_i$.
Approximate index partial \(\Theta(1)\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} = \Theta(1)$, both sides having constant certificates.
Collision problem partial \(O(n)\) At most $\mathrm{C} = n/2+1$; from below $\mathrm{rdeg} \ge \mathrm{ndeg} = 2$ and $\mathrm{rdeg} \ge \widetilde{\mathrm{rdeg}}$.
Element distinctness total \(\Theta(n)\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$. The two sides are wildly asymmetric: $\mathrm{ndeg}(\bar f) \le 2$, since $\sum_{i<j}\sum_v x_{i,v}x_{j,v}$ counts colliding pairs and so is nonzero exactly when a collision exists, while $\mathrm{ndeg}(f) = \Theta(n)$. The max is $\Theta(n)$, matching $\mathrm{rdeg} \le \mathrm{C} = n$.
Ambainis-Belovs function partial \(O(1)\) Take $p$ to be the degree-$9$ exact representation and $q = 1$: a rational representation of degree $9$. So $\mathrm{rdeg} \le \deg \le 9$ while $\mathrm{Q} = \Omega(n^{1/3})$.
Surjectivity total \(\Omega(n/\log n),\ O(n)\) putative $\mathrm{rdeg}(f)=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}\le\mathrm{C}(f)=\Theta(n)$. For the lower end, restrict as in \(\deg_2(f)\) but also fix all but one bit of each free slot to $1$: the restriction of $\bar f$ is $\mathrm{NOR}_{R+1}$, and a polynomial nonzero exactly at $0^t$ must be a multiple of $\prod_i(1-y_i)$, so $\mathrm{ndeg}(\bar f)\ge R+1=\Theta(n/\log n)$. deWolf03
Triangle finding total \(\Theta(m^2)\) putative $\mathrm{rdeg}=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}\le\mathrm{C}=\binom m2$. The complement side is the expensive one: on the restriction of \(\deg_2(f)\) the complement is $\mathrm{NOR}_t$ with $t=\binom{m-1}2$, and a polynomial nonzero exactly at $0^t$ is a multiple of $\prod_i(1-x_i)$, so $\mathrm{ndeg}(\bar f)\ge\binom{m-1}2$. deWolf03
Ordered search partial \(1\) $\mathrm{rdeg}=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$ [deWolf03], and both sides are $1$ by the \(\mathrm{ndeg}(f)\) argument applied to $f$ and to its complement (shift the alternating partial sums by one). deWolf03
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{rdeg}_{\varepsilon}(f) \le \mathrm{rdeg}(f) \le \mathrm{C}(f)$, with $\mathrm{rdeg}_{\varepsilon} = \Theta(n)$ and $\mathrm{C} = n$. So IP is one of the functions on which Fortnow's question -- is $\mathrm{rdeg} = \deg^{\Omega(1)}$? -- has the most boring possible answer.
Minsky-Papert one-in-a-box total \(m^2 = N^{2/3}\) putative $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$. The complement side dominates: filling every other box with a $1$ restricts $\overline{\mathrm{MP}}$ to $\mathrm{NOR}_{m^2}$, whose nondeterministic degree is $m^2$ (a polynomial nonzero exactly at $0^{k}$ is a multiple of $\prod_i(1-x_i)$), and $\mathrm{ndeg}(\bar f) \le \mathrm{C}^0 = m^2$. So $\mathrm{rdeg} = m^2 = \mathrm{C}$, a cube root below $\deg = N$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) putative Sandwiched: $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \ge m-1$, and $\mathrm{rdeg}(f) \le \mathrm{C}(f) = m$. (For the record the complement is no harder: at most one vertex is a sink, so $\overline{\mathrm{SINK}} = 1 - \sum_v \prod_{u\ne v}[u\to v]$ on the nose, giving $\mathrm{ndeg}(\bar f) \le m-1$ as well.)
Scorpion graphs total \(\Theta(m)\) Sandwiched: $\mathrm{ndeg}(f) \le \mathrm{rdeg}(f) \le \deg(f)$, with $\mathrm{ndeg} = \Theta(m)$ and $\deg = 3m-6$ here. Rational functions buy nothing exactly, just as they buy nothing on \(\mathrm{CONN}_m\).
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) putative Rational functions buy essentially nothing. Use the characterisation $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \mathrm{C}(f)$: the $0$-side is expensive, since fixing all pairs inside a balanced bipartition $(A,B)$ to present and leaving the $\lfloor m^2/4\rfloor$ crossing pairs free makes the restriction $\mathrm{OR}$, whence $\mathrm{ndeg}(\bar f) \ge \mathrm{ndeg}(\mathrm{NOR}_{\lfloor m^2/4\rfloor}) = \lfloor m^2/4\rfloor$; and $\mathrm{C} = \Theta(m^2)$ caps it. Contrast $\mathrm{ndeg} = m-1$: the asymmetry between spanning trees and cuts is exactly what rational degree cannot exploit.
AND of complemented EXACT-ONE functions total \(m\) Theorem 10. KLLPV26