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

Mod-p degree

Degree over F_p.

Definition

Least degree of a polynomial over $\mathbb{F}_p$ agreeing with $f$ on the domain.

Parameters

\(p\) (p) default \(2\)

prime modulus

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\deg_p(f)\). “\(\deg_p(f)\) in terms of it” is the pair with \(\deg_p(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_p(f)\) in terms of it It in terms of \(\deg_p(f)\)
\(\deg_2(f)\) Mod-2 degree total1,? derived open pair → total1,? derived open pair →
\(\deg(f)\) Exact degree total1,1 partial1,1 open pair → total1,? partial∞ derived open pair →
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity total1,? partial1,? derived open pair → total1,? partial1,? derived open pair →

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

Known values

FunctionValueNotes
OR total \(n\) For every prime $p$. Over $\mathbb{F}_p$ the multilinear representation is still $1 - \prod_i(1 - x_i)$, which contains $x_1\cdots x_n$ with coefficient $(-1)^{n+1} \ne 0$. Unlike \(\oplus_n\), OR gets no help from small characteristic -- which is why the value can be recorded as a bare $n$ with no choice of $p$ to make.
AND total \(n\) For every prime $p$: $\mathrm{AND} = \prod_i x_i$ over every field, so there is no choice of $p$ to make and the value is a bare $n$.
PARITY total \(1 \text{ if } p = 2;\ n \text{ if } p > 2\) Over $\mathbb{F}_2$ parity is the linear form $\sum_i x_i$. For odd $p$ the multilinear representation is $\tfrac12\big(1 - \prod_i(1-2x_i)\big)$, whose top coefficient $\pm 2^{n-1}$ is a unit mod $p$, so the degree jumps back to $n$. This single function is the whole content of the $\deg_p$ column.
MAJORITY total \((n+1)/2 \text{ for } p = 2,\ n = 2^m - 1\) The $\mathbb{F}_2$ multilinear expansion of the threshold $\mathrm{Th}_k^n$ is $\sum_{|S| \ge k} \binom{|S|-1}{k-1}\prod_{i \in S} x_i$. By Lucas' theorem $\binom{s-1}{k-1}$ is odd iff the binary digits of $k-1$ are a submask of those of $s-1$; with $n = 2^m-1$ and $k = 2^{m-1}$ the only $s-1 \le n-1$ containing the mask $0\underbrace{1\cdots1}_{m-1}$ is $2^{m-1}-1$ itself, so the degree is exactly $2^{m-1} = (n+1)/2$. For $n = 3$ this is the familiar $\mathrm{MAJ}_3 = xy + yz + zx$.
Threshold total \(\Theta(n)\) putative For every prime $p$. Over the integers $\mathrm{THR}^n_k = \sum_{|S| \ge k} (-1)^{|S|-k}\binom{|S|-1}{k-1}\prod_{i \in S} x_i$ (the \(\deg(f)\) line), and reducing this unique multilinear form mod $p$ shows $\deg_p = \max\{s \le n : \binom{s-1}{k-1} \not\equiv 0 \bmod p\}$. Taking $s = k$ gives the coefficient $\binom{k-1}{k-1} = 1$, so $\deg_p \ge k$; substituting $x_i \mapsto 1-x_i$ preserves degree and maps $\mathrm{THR}^n_k$ to the complement of $\mathrm{THR}^n_{n-k+1}$, so also $\deg_p \ge n-k+1$. Hence $\deg_p \ge \max\{k,\ n-k+1\} \ge (n+1)/2$, and $\deg_p \le n$. No prime helps, in contrast with \(\mathrm{ADDR}_k\).
EXACT-HALF total \(\Theta(n)\) putative For every prime $p$. The coefficient of $\prod_{i \in S}x_i$ in the integer multilinear expansion is $(-1)^{|S|-n/2}\binom{|S|}{n/2}$, so $\deg_p$ is the largest $s \le n$ with $\binom{s}{n/2} \not\equiv 0 \pmod p$. Taking $s = n/2$ gives $\binom{n/2}{n/2} = 1$, so $\deg_p \ge n/2$ in every characteristic, and $\deg_p \le n$ trivially. Which $s$ is largest jumps around with $p$ and $n$ by Lucas -- see the \(\deg_2(f)\) line for the $p=2$ story -- but the order is always $n$.
ODD-MAX-BIT total \(n\) putative For every prime $p$. The expansion $\mathrm{OMB} = \sum_{i \text{ odd}} x_i\prod_{j>i}(1-x_j)$ has the top monomial $x_1\cdots x_n$ only from the $i=1$ term, with coefficient $(-1)^{n-1}$, which is nonzero in every characteristic. So small characteristic buys nothing, exactly as for \(\mathrm{OR}_n\).
ADDRESS / multiplexer total \(k+1\) putative For every prime $p$: the expansion $\sum_a \big(\prod_{i:a_i=1} z_i \prod_{i:a_i=0}(1-z_i)\big) y_a$ used for $\deg_2$ has top monomials $z_1\cdots z_k\,y_a$ with coefficient $\pm1$, nonzero in every characteristic, and they cannot cancel because they carry distinct table variables.
Binary tree navigation total \(k\) putative The recursion $\mathrm{Nav}_k = L + x_0(R-L)$ over $\mathbb{F}_p$: by induction $R$ carries a degree-$(k-1)$ monomial with coefficient $\pm1$ in variables disjoint from those of $L$, so $x_0$ times it survives with coefficient $\pm1 \ne 0$ for every $p$. Unlike \(\oplus_n\) and \(\mathrm{MAJ}_n\), navigation gets no discount in any characteristic.
TRIBES total \(n\) putative For every prime $p$. Over $\mathbb{F}_p$ the representation is still $1 - \prod_j(1 - \prod_{i\in T_j} x_i)$, whose top monomial $x_1\cdots x_n$ has coefficient $(-1)^{s+1} \ne 0$ in every characteristic. Consistent with the $\deg_2 = n$ entry above.
AND-OR tree (depth 2) total \(N = n^2\) putative For every prime $p$. Over $\mathbb{F}_p$ one has $\mathrm{OR}_n(y) = 1-\prod_i(1-y_i)$, whose top monomial $\prod_i y_i$ carries coefficient $(-1)^{n+1}$, and $\mathrm{AND}_n$ is the plain product of its arguments; the blocks are disjoint, so the top monomial $\prod_{i,j}x_{ij}$ of the composition survives with coefficient $((-1)^{n+1})^n \ne 0$. Hence $\deg_p = \deg = N$ for all $p$, matching the recorded $\deg_2$.
NAND tree (balanced AND-OR formula) total \(N\) putative For every prime $p$. Over $\mathbb{F}_p$, $\mathrm{NAND}(u,v) = 1-uv$, so if $c_{d-1}$ is the coefficient of the top monomial of $f_{d-1}$ then $c_d = -c_{d-1}^2$; starting from $c_0 = 1$ this stays $\pm 1$ and never vanishes mod $p$. Hence $\deg_p = \deg = N$ for all $p$, consistent with the recorded $\deg_2 = N$.
Kushilevitz's function (iterated) total \(3^k = N^{0.6131}\) putative For every prime $p$. In the $0/1$ multilinear expansion $K = \tfrac12 - \tfrac18(\sum_{T\in\mathcal{F}}\chi_T - \sum_i\chi_i)$ with $\chi_S = \prod_{i\in S}(1-2x_i)$, the degree-$3$ part of $\chi_T$ is $-8\prod_{i\in T}x_i$, so each of the ten monomials $\prod_{i\in T}x_i$ carries coefficient exactly $+1$ -- nonzero modulo every $p$. Under self-composition the top-degree part is $\sum_{T\in\mathcal{F}}\prod_{i\in T}(\text{top part of the } i\text{-th copy})$, a sum of distinct monomials over disjoint blocks, so no cancellation is possible and $\deg_p = 3^k$ for all $p$, matching the recorded $\deg_2$.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Same integrality argument as the $\deg_2$ line, for every prime $p$: $\deg_p\le\deg=\widetilde O(\sqrt n)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n)\) Same integrality argument as the $\deg_2$ line, for every prime $p$.
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) Same integrality argument as the $\deg_2$ line, for every prime $p$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) Same integrality argument as the $\deg_2$ line, for every prime $p$.
Ambainis' exact-quantum function total \(2^d\) putative Exact for every prime $p$. The multilinear representation over any field is unique on $\{0,1\}^n$ and is the reduction of the integer one obtained by Mobius inversion, so $\deg_p\le\deg=2^d$ with equality iff the top coefficient survives mod $p$. Here the real form is $\mathrm{NE}=x_1+x_2+x_3-(x_1x_2+x_1x_3+x_2x_3)$ and a top-degree coefficient obeys $c_d=-c_{d-1}^2$ with $c_0=1$, so $|c_d|=1$ and it is nonzero modulo every $p$.
Surjectivity total \(\Theta(n)\) putative Same restriction as \(\deg_2(f)\): over $\mathbb{F}_p$ the restriction $\mathrm{OR}_{R+1}\circ\mathrm{AND}_{\log_2 R}$ is $1-\prod_i(1-\prod_j x_{ij})$, whose top monomial has coefficient $\pm1\ne0$, so $\deg_p\ge(R+1)\log_2 R=\Theta(n)$; and $\deg_p\le\deg=n$.
Triangle finding total \(\Theta(m^2)\) putative Same restriction as \(\deg_2(f)\): $\mathrm{OR}_t=1-\prod_i(1-x_i)$ has $\mathbb{F}_p$-degree $t=\binom{m-1}2$, and $\deg_p\le\deg\le\binom m2$.
Ordered search partial \(1\) putative Same construction as the $\deg=1$ entry, over $\mathbb{F}_p$: with $p(x)=\sum_i c_ix_i$ one has $p(x^{(k)})=\sum_{i>k}c_i$, and choosing $c_i=\pm1$ alternating makes the partial sums alternate between $0$ and $1$, which is $k\bmod 2$ on the promise.
Inner product mod 2 total \(2 \text{ for } p = 2;\ n \text{ for } p > 2\) Over $\mathbb{F}_2$ the inner product literally is $\sum_{i} x_i y_i$, a quadratic form -- degree $2$ on $n = 2m$ variables. Over any other field the representation is $\tfrac12\big(1 - \prod_i (1 - 2x_iy_i)\big)$ and the degree is $n$. Together with $\deg = n$, $\mathrm{s} = n$ and $\mathrm{D} = n$, this makes IP the standard example that $\deg_2$ carries no information about query complexity.
Minsky-Papert one-in-a-box total \(N = m^3\) putative For every prime $p$. The multilinear representation has integer coefficients, and its top coefficient is $\prod_{j}\big(\!-(-1)^{m^2}\big) = \pm1$, which survives reduction mod any $p$. So unlike \(\mathrm{IP}_n\) and \(\mathrm{CONN}_m\), MP loses no degree over any finite field.
Sink of a tournament total \(m-1 = \Theta(\sqrt N)\) putative For every prime $p$, by the same disjoint decomposition that gives $\deg$ and $\deg_2$: the $m$ star monomials are distinct sets and each carries coefficient $\pm1$ over $\mathbb{Z}$, so nothing cancels in any characteristic.
Scorpion graphs total \(3m-6 \text{ for } p \ge 5\) putative Reduce the integer multilinear polynomial mod $p$: the top coefficient of $\prod_{e \in T}x_e$ is exactly $-6$, the six orderings of one triple $\{s,t,b\}$ each contributing $-1$ (see \(\deg(f)\)), so it survives modulo every prime $p \ge 5$ and $\deg_p = \deg = 3m-6$. It does not survive mod $2$ or mod $3$, and indeed exhaustive computation gives $\deg_2 = 6,\,10,\,13$ at $m = 5,6,7$ against $3m-6 = 9,\,12,\,15$ -- small characteristic genuinely helps on the scorpion, which is why \(\deg_2(f)\) is left unrecorded rather than guessed.
Graph connectivity total \(N \text{ for } p \ge m\) putative The top coefficient of the multilinear expansion is $\pm(m-1)!$ (see \(\deg(f)\)), invertible modulo every prime $p \ge m$, so $\deg_p = \deg = N$ there. For small primes it does vanish, and dramatically so: \(\deg_2(f)\) is only $\lfloor m^2/4\rfloor$.