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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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. |