Q The Query Complexity Zoo
\(\mathrm{D}^{\oplus}(f)\)

Parity decision tree complexity

Decision tree depth when each query may read the parity of an arbitrary subset of bits.

also written: D_parity, linear decision tree complexity over F_2

Definition

Each internal node is labelled by a set $S \subseteq [n]$ and branches on $\bigoplus_{i\in S} x_i$. $\mathrm{D}^{\oplus}(f)$ is the minimum depth. Clearly $\mathrm{D}^{\oplus}(f) \le \mathrm{D}(f)$, and $\mathrm{D}^{\oplus}$ can be exponentially smaller (e.g. $\mathrm{D}^\oplus(\mathrm{PARITY}_n)=1$). This is the query model tied to the log-rank conjecture through lifting.

Basic facts

  • $\mathrm{D}^{\oplus}(f) \ge \tfrac12\log_2 \mathrm{spar}(f)$: a depth-$d$ parity tree has $\le 2^d$ leaves, each the indicator of a coset of a codimension-$\le d$ subspace, whose Fourier support has size $\le 2^d$; so $\mathrm{spar}(f) \le 4^{\,d}$.
  • Whether the converse $\mathrm{D}^{\oplus}(f) = \mathrm{polylog}\,\mathrm{spar}(f)$ holds -- the log-rank conjecture for parity decision trees -- is a major open problem.
  • $\mathrm{D}^{\oplus}(f) = O(\sqrt{\mathrm{spar}(f)}\,\log \mathrm{spar}(f))$ is known for total $f$.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{D}^{\oplus}(f)\). “\(\mathrm{D}^{\oplus}(f)\) in terms of it” is the pair with \(\mathrm{D}^{\oplus}(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{D}^{\oplus}(f)\) in terms of it It in terms of \(\mathrm{D}^{\oplus}(f)\)
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 relation1,1 open pair → total∞ partial∞ relation∞ derived open pair →
\(\mathrm{spar}(f)\) Fourier sparsity totallog,0.5 open pair → totalexp,? derived open pair →
\(\hat{L}_1(f)\) Spectral norm total∞ derived open pair → totalexp,? derived open pair →
\(\deg_2(f)\) Mod-2 degree total∞ derived open pair → total1,1 open pair →

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

Known values

FunctionValueNotes
OR total \(n\)
AND total \(n\) putative Parity queries are unaffected by complementing the input (a parity of a set shifts by a constant), so $\mathrm{D}^{\oplus}(\mathrm{AND}_n) = \mathrm{D}^{\oplus}(\mathrm{OR}_n) = n$.
PARITY total \(1\) One parity query. The reason $\mathrm{D}^{\oplus}$ is a genuinely different measure.
MAJORITY total \(n - \mathrm{B}(n) + 1\) Exactly, where $\mathrm{B}(n)$ is the number of ones in the binary expansion of $n$. Lower bound from granularity: every Fourier coefficient of $\mathrm{MAJ}_n$ is an integer multiple of $2^{-k}$ with $k = n - \mathrm{B}(n)$, and [ChistopolskayaPodolskii18] show $\mathrm{D}^{\oplus} \ge k+1$. Parity queries buy $\mathrm{B}(n)-1$ queries off $\mathrm{D} = n$, and no more. ChistopolskayaPodolskii18
Threshold total \(\Theta(n)\) putative Between $n - \log_2 n$ and $n$. Upper: $\mathrm{D}^{\oplus} \le \mathrm{D} = n$. Lower by granularity: in the $\pm1$ encoding the top Fourier coefficient is $\pm 2^{1-n}\binom{n-1}{k-1}$ (the \(\deg(f)\) line), so the granularity is at least $n-1-\nu_2\binom{n-1}{k-1}$, and $\mathrm{D}^{\oplus} \ge \mathrm{gran}+1$ [ChistopolskayaPodolskii18]. By Kummer's theorem $\nu_2\binom{n-1}{k-1}$ counts the carries when adding $k-1$ and $n-k$ in base $2$, hence is at most $\log_2 n$. At $k = (n+1)/2$ this reproduces the exact $n - \mathrm{B}(n) + 1$ recorded for \(\mathrm{MAJ}_n\); parity queries never help a threshold. ChistopolskayaPodolskii18
EXACT-HALF total \(\Theta(n)\) putative Upper: $\mathrm{D}^{\oplus} \le \mathrm{D} = n$. Lower by granularity: in the $\pm1$ encoding the top coefficient is $\hat g([n]) = \mp\binom{n}{n/2}2^{1-n}$, and $\nu_2\binom{n}{n/2}$ equals the number of carries in adding $n/2 + n/2$ in base $2$, namely the binary digit sum of $n/2$ (Kummer). So the granularity is at least $n-1-\log_2 n$ and $\mathrm{D}^{\oplus} \ge n - \log_2 n$. Along $n = 2^m$ the digit sum is $1$, pinning $\mathrm{D}^{\oplus}$ to $n-1$ or $n$: parity queries buy at most one query on the middle slice. ChistopolskayaPodolskii18
ODD-MAX-BIT total \(n\) putative At most $\mathrm{D} = n$. For the lower bound, take the $\pm1$-valued $g = 1-2\mathrm{OMB}$: in the expansion $\mathrm{OMB} = \sum_{i \text{ odd}} x_i\prod_{j>i}(1-x_j)$ only the $i=1$ term involves $x_1$, so it alone determines $\hat g(S)$ for every $S \ni 1$, and each such coefficient is exactly $\pm 2^{-(n-1)}$. The granularity is therefore exactly $n-1$, and the bound $\mathrm{D}^{\oplus} \ge \mathrm{gran}+1$ of [ChistopolskayaPodolskii18] gives $n$. So parity queries buy nothing, even though $\mathrm{sdeg} = 1$. ChistopolskayaPodolskii18
ADDRESS / multiplexer total \(\Theta(k)\) putative Upper: $\mathrm{D}^{\oplus} \le \mathrm{D} = k+1$. Lower: a depth-$d$ parity decision tree has at most $2^d$ leaves, each an affine subspace of codimension $\le d$ whose indicator has Fourier support of size $2^d$, so $\mathrm{spar}(f) \le 4^{d}$; with $\mathrm{spar} = 4^k$ this forces $d \ge k$. Parity queries save at most one query on the multiplexer.
Binary tree navigation total \(k\) putative At most $\mathrm{D} = k$. For the lower bound, the recursion above makes every nonzero Fourier coefficient exactly $\pm 2^{-(k-1)}$, so the granularity is $k-1$ and the granularity bound $\mathrm{D}^{\oplus} \ge \mathrm{gran} + 1$ of [ChistopolskayaPodolskii18] gives $k$. Parity queries buy nothing at all here. ChistopolskayaPodolskii18
TRIBES total \(n\) putative At most $\mathrm{D} = n$. For the lower bound, the $0/1$ representation $1-\prod_j(1-\prod_{i\in T_j}x_i)$ has top monomial coefficient $(-1)^{s+1} = \pm1$, so the $\pm1$-valued $g = 1-2f$ has $\hat g([n]) = \pm2^{-(n-1)}$ -- the largest granularity an $n$-bit function can have -- and $\mathrm{D}^{\oplus} \ge \mathrm{gran}+1 = n$ [ChistopolskayaPodolskii18]. Parity queries buy nothing. ChistopolskayaPodolskii18
AND-OR tree (depth 2) total \(N = n^2\) putative Parity queries buy nothing: $\deg_2 \le \mathrm{D}^{\oplus} \le \mathrm{D}$, and the recorded $\deg_2 = \mathrm{D} = N$ closes the sandwich.
NAND tree (balanced AND-OR formula) total \(N\) putative Parity queries buy nothing. In the $\pm1$ encoding each $\mathrm{NAND}_2$ gate has all four Fourier coefficients equal to $\pm\tfrac12$, and because the two subtrees are on disjoint variables every coefficient of $f_d$ is a product of one coefficient per gate on the relevant part of the tree. The coefficient of the full set uses all $N-1$ gates, so it equals $\pm 2^{-(N-1)}$ and the granularity is exactly $N-1$. [ChistopolskayaPodolskii18] give $\mathrm{D}^{\oplus} \ge k+1$ at granularity $2^{-k}$, so $\mathrm{D}^{\oplus} \ge N$, and $\mathrm{D}^{\oplus} \le \mathrm{D} = N$ closes it. Contrast \(\mathrm{MAJ}_3^{\circ d}\), where the same argument gives exactly $(N+1)/2$. ChistopolskayaPodolskii18
Recursive MAJORITY-of-3 total \((N+1)/2 = (3^d+1)/2\) Exactly. The granularity of $\mathrm{MAJ}_3^{\circ d}$ is $2^{-(N-1)/2}$, and [ChistopolskayaPodolskii18] show $\mathrm{D}^{\oplus}\ge k+1$ for granularity $2^{-k}$; the matching parity decision tree is explicit. So parity queries halve the cost here, unlike on \(\oplus_n\) (where they collapse it) or \(\mathrm{IP}_n\) (where they buy a factor $2$ at most). ChistopolskayaPodolskii18
Kushilevitz's function (iterated) total \(\Omega(N^{0.6131}),\ O(N)\) putative Not pinned. Upper: $\mathrm{D}^{\oplus}\le\mathrm{D}=N$. Lower by granularity: every coefficient of $K^{\circ k}$ is a product of base coefficients, each exactly $\pm\tfrac14$, and the number of factors obeys $F_k = 1 + 3F_{k-1}$ (choose one of the ten triples at every level), so the extreme coefficient is $\pm 4^{-(3^k-1)/2} = \pm 2^{-(3^k-1)}$ and the granularity is exactly $3^k-1$. [ChistopolskayaPodolskii18] then give $\mathrm{D}^{\oplus} \ge 3^k = \deg$. Parity queries can therefore save at most the $N^{0.39}$ by which $\deg$ falls short of $\mathrm{D}$. ChistopolskayaPodolskii18
Rubinstein's function total \(\Theta(N)\) putative Parity queries do not help: $\deg_2 \le \mathrm{D}^{\oplus} \le \mathrm{D}$, and the recorded $\deg_2 = \Theta(N)$, $\mathrm{D} = N$ close the sandwich.
Ambainis-Sun function total \(\Theta(N)\) putative $\deg_2 \le \mathrm{D}^{\oplus} \le \mathrm{D}$, and the recorded $\deg_2 = (3k+2)^2 = \Theta(N)$ and $\mathrm{D} = \Theta(N)$ close the sandwich: parity queries buy nothing.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) putative $\deg_2 \le \mathrm{D}^{\oplus} \le \mathrm{D}$, and the recorded $\deg_2 = \Theta(n^2)$ and $\mathrm{D} = \Theta(n^2)$ close the sandwich. Consistent with the recorded $\dim_{\mathbb{F}_2} = n^2-n$.
Ambainis' exact-quantum function total \(\Omega(2^d),\ O(3^d)\) Floor $\mathrm{D}^{\oplus}\ge\deg_2=2^d$: the leaves of a depth-$k$ parity decision tree are products of $k$ affine forms, so the $\mathbb{F}_2$-degree is at most $k$. Ceiling $\mathrm{D}^{\oplus}\le\dim_{\mathbb{F}_2}=2\cdot3^{d-1}$ (query the relevant parities). Parity queries do help a little: already $\mathrm{D}^{\oplus}(\mathrm{NE})=2<3=\mathrm{D}(\mathrm{NE})$, via $\mathrm{NE}=\mathrm{OR}(x_1\oplus x_2,x_2\oplus x_3)$.
Bernstein-Vazirani partial \(n\) putative Parity queries buy nothing. A query on a set $S$ of positions returns $\bigoplus_{i \in S}\langle s, i\rangle = \langle s, \sum_{i \in S} i\rangle$ -- again a single linear functional of $s$ -- so $q$ queries reveal at most $q$ bits about the $n$-bit secret and $\mathrm{D}^{\oplus} \ge n$; and $\mathrm{D}^{\oplus} \le \mathrm{D} = n$. The Hadamard promise is precisely the fixed point of the parity model.
Unstructured search (relation) relation \(n\) putative Parity queries do not help. Along the branch where every answer is $0$, the queried sets $S_1,\dots,S_q$ are fixed; outputting $\bot$ is correct only if $0^n$ is the unique input consistent with those answers, i.e. only if $S_1,\dots,S_q$ span $\mathbb{F}_2^n$, forcing $q \ge n$. And $\mathrm{D}^{\oplus} \le \mathrm{D} = n$. Contrast $\mathrm{D}^{\oplus}(\mathrm{PARITY}) = 1$: what parity queries cannot do is locate a one.
FIND-1 under a density promise relation \(\Theta(n)\) putative At least $n/2$, so parity queries are as useless as ordinary ones. Answer $0$ to every query; after $q$ queries the consistent inputs form the linear space $W^{\perp}$, $\dim = n-q$, where $W$ is the span of the queried sets. A leaf that outputs $i$ must have $x_i = 1$ throughout $W^{\perp} \cap \{|x| \ge n/2\}$, but $V = W^{\perp} \cap \{x_i = 0\}$ has dimension $\ge n-q-1$, and any subspace of dimension $d$ contains a vector of weight $\ge d$ (sum the reduced-echelon basis: it is $1$ on all $d$ pivots). For $q \le n/2 - 1$ that vector satisfies the promise and refutes the leaf. And $\mathrm{D}^{\oplus} \le \mathrm{D} = n/2+1$. Against $\mathrm{R} = O(1)$ this is the same unbounded gap as for $\mathrm{D}$.
Approximate Hamming weight relation \(\Theta(n)\) putative Parity queries do not count either. After $q$ parity queries the consistent inputs form an affine space $A$ of dimension $n-q$; choosing $n-q$ free coordinates, every pattern on them occurs, so $A$ contains an input of weight $\le q$ (free part all $0$) and one of weight $\ge n-q$ (free part all $1$). A leaf can name one valid $w$ only if the weights inside $A$ span at most $2\varepsilon n$, forcing $n - 2q \le 2\varepsilon n$, i.e. $\mathrm{D}^{\oplus} \ge (1-2\varepsilon)n/2$. And $\mathrm{D}^{\oplus} \le \mathrm{D} = \Theta(n)$.
Gap-Majority partial \(\Theta(n)\) putative Parity queries are no better than plain ones. After $q$ parity queries the consistent inputs form an affine space $A$ of dimension $n-q$; picking $n-q$ free coordinates, $A$ contains an input of weight $\le q$ and one of weight $\ge n-q$. If $q < n/2-\delta n$ these are a $0$-input and a $1$-input of the promise, so no leaf can decide, giving $\mathrm{D}^{\oplus} \ge (1/2-\delta)n$; and $\mathrm{D}^{\oplus} \le \mathrm{D} = \Theta(n)$.
Gap-Majority at constant gap partial \(\Theta(n)\) putative Parity queries do not help: after $q < n/4$ of them the consistent affine space still contains inputs of both values. See \(\mathrm{GapMaj}^{\delta}_{n}\).
Surjectivity total \(\Theta(n)\) A depth-$t$ parity tree writes $f$ over $\mathbb{F}_2$ as a sum of products of at most $t$ affine forms, so $\deg_2\le\mathrm{D}^{\oplus}$; with $\deg_2=\Theta(n)$ and $\mathrm{D}^{\oplus}\le\mathrm{D}=n$ there is no room. Parity queries buy nothing on surjectivity.
Triangle finding total \(\Theta(m^2)\) $\deg_2\le\mathrm{D}^{\oplus}\le\mathrm{D}$: a depth-$t$ parity tree writes $f$ as a sum of products of at most $t$ affine forms over $\mathbb{F}_2$. With $\deg_2=\Theta(m^2)$ and $\mathrm{D}=\binom m2$ the two ends meet.
Fourier fishing relation \(\Omega(\log N),\ O(N)\) putative Upper: $\mathrm{D}^{\oplus}\le\mathrm{D}=N$. Lower: answer counting. For each $z$ the truth table $f=\chi_z$ has $z$ as its only valid answer, so a tree needs at least $N$ leaves and hence depth $\ge\log_2 N$. Whether parity queries actually help is open -- a parity of truth-table cells is not a Fourier coefficient.
Ordered search partial \(1\) putative One parity query. On the promise $x=0^k1^{n-k}$ the decision version is $\mathrm{OS}^{\oplus}=k\bmod 2=(n\bmod 2)\oplus\bigoplus_i x_i$, so the single query $\bigoplus_{i\in[n]}x_i$ settles it, against $\mathrm{D}=\lceil\log_2(n+1)\rceil$. The same identity is why $\deg=1$.
Tseitin search on an expander relation \(\Theta(\log n)\) putative Exponentially cheaper than $\mathrm{D}=\Theta(n)$. For a vertex set $S$, $\sum_{v\in S}(\chi(v)+\sum_{e\ni v}x_e)=\chi(S)+\sum_{e\in\partial S}x_e$ over $\mathbb{F}_2$, since interior edges are counted twice -- one parity query tells whether $S$ contains an odd number of violated vertices. Starting from $S=V$, which is odd because the total charge is odd, halving $S$ each time isolates a violated vertex in $\lceil\log_2|V|\rceil$ queries. Matching lower bound by answer counting: the violation vector is $Ax+\chi$, which ranges over all odd-weight vectors, so each single vertex $v$ is the unique answer for some input and the tree needs $|V|=\Theta(n)$ leaves.
Inner product mod 2 total \(\ge n/2 + 1\) The granularity of IP is exactly $2^{-n/2}$, so [ChistopolskayaPodolskii18] gives $\mathrm{D}^{\oplus} \ge n/2 + 1$. Upper bound: the trivial $n$. The factor $2$ is open as far as I know -- note $\mathrm{D}^{\oplus} \ge n/2$ also follows from bentness, since an affine subspace on which a bent function is constant has dimension at most $n/2$. ChistopolskayaPodolskii18
Minsky-Papert one-in-a-box total \(N = m^3\) Pinned exactly: a depth-$d$ parity decision tree computes a function of $d$ linear forms, so $\deg_2(f) \le \mathrm{D}^{\oplus}(f) \le \mathrm{D}(f)$, and $\deg_2 = \mathrm{D} = N$ here. Parity queries are useless on a read-once AND-OR formula.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) putative Lower: $\mathrm{spar}(f) \le 4^{\mathrm{D}^{\oplus}(f)}$ with $\mathrm{spar} = \Theta(m2^m)$ gives $\mathrm{D}^{\oplus} \ge (m-1)/2$. Upper: $\mathrm{D}^{\oplus} \le \mathrm{D} = O(m)$. Parity queries buy nothing, which is the query-level shadow of the [CMS19] refutation: $\mathrm{SINK}$ has tiny spectral norm yet its parity decision trees are as deep as its ordinary ones.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Sandwiched: $\deg_2(f) \le \mathrm{D}^{\oplus}(f) \le \mathrm{D}(f)$, with $\deg_2 = \lfloor m^2/4\rfloor$ and $\mathrm{D} = N$ here. Parity queries save at most the factor $2$ that $\mathbb{F}_2$-degree already saves -- connectivity is evasive up to a constant even for parity decision trees.