Q The Query Complexity Zoo
\(\bar{\wedge}\text{-tree}\)

NAND tree (balanced AND-OR formula)

The Saks-Wigderson function: $\mathrm{R}_0 = \Theta(N^{0.7537})$, $\mathrm{Q}=\Theta(\sqrt N)$, $\deg = N$.

total composed arity: $N = 2^d$ leaves— also: Saks-Wigderson function, balanced binary NAND formula, read-once AND-OR formula

Description

A complete binary tree of depth $d$ whose leaves are the input bits and whose internal gates are all NAND. Equivalently, the balanced read-once AND-OR formula with alternating levels.

Formal definition

$$f_0(x)=x,\qquad f_{k}(x^{(1)},x^{(2)}) = \neg\big(f_{k-1}(x^{(1)}) \wedge f_{k-1}(x^{(2)})\big),$$ and $f = f_d$ on $N=2^d$ variables.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(N\)
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta\!\big(N^{\,0.753\ldots}\big)\) The exponent is $\log_2\!\frac{1+\sqrt{33}}{4} = 0.75366\ldots$. Upper bound [SaksWigderson86], matching lower bound [SaksWigderson86]; [Santha95] extends the lower bound to bounded error. SaksWigderson86 Santha95
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta\!\big(N^{\,0.753\ldots}\big)\) Santha95
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(\sqrt{N})\) Continuous-time algorithm [FGG08], discrete-query version [ACRSZ10]; lower bound from $\lambda$. FGG08 ACRSZ10
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(N)\) $\ge \deg/2$.
\(\deg(f)\) Exact degree \(N\) True of any read-once formula.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(\sqrt{N})\)
\(\mathrm{s}(f)\) Sensitivity \(\Theta(\sqrt{N})\)
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(\sqrt{N})\)
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(\sqrt{N})\)
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(\sqrt{N})\)
\(\lambda(f)\) Spectral sensitivity \(\sqrt{N}\) $\lambda(\mathrm{NAND}_2)=\sqrt2$ and $\lambda$ is multiplicative.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(\sqrt N)\) Between $\mathrm{bs}$ and $\mathrm{C}$, which agree here.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(\sqrt N)\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(\sqrt N)\) Between $\mathrm{fbs}$ and $\mathrm{C}$, which agree here.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(N\)
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(\sqrt{N})\) $\mathrm{CA}(f) = \Theta(\mathrm{RC}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{RC}(f) = \Theta(\sqrt{N})$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(\sqrt{N})\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{RC}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{RC}(f) = \Theta(\sqrt{N})$ here.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(\sqrt{N})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(\sqrt{N})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(\sqrt{N})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\lambda(f) = \sqrt{N}$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{N})$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\sqrt{N})\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{N})$ here.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(\sqrt{N})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \sqrt{N}$ and $\mathrm{Adv}^{\pm}(f) = \Theta(\sqrt{N})$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta\!\big(N^{\,0.753\ldots}\big)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{R}_{0}(f)$, with both ends $\Theta\!\big(N^{\,0.753\ldots}\big)$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta\!\big(N^{\,0.753\ldots}\big)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{R}_{0}(f)$, with both ends $\Theta\!\big(N^{\,0.753\ldots}\big)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\sqrt{N})\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt{N})$ here.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\tilde\Theta\!\big(N^{\,0.753\ldots}\big)\) The conical junta composition theorem gives $\tilde\Omega(N^{0.753\ldots})$, answering a question of Beame and Lawry; the matching upper bound is $\mathrm{cjdeg} \le \mathrm{R}$. So on the binary AND-OR tree the nonnegative LP is already tight up to logs -- unlike $\widetilde{\deg} = \Theta(\sqrt N)$, which is quadratically off. GoosJayram16
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\big(\tfrac{1+\sqrt{33}}{4}\big)^{d} = N^{0.753\ldots}\) One of the few entries in the zoo that is a number rather than a $\Theta$-class. Because $(\mathrm{NANDtree}_d)^{\circ k} = \mathrm{NANDtree}_{dk}$ and $\mathrm{R}(\mathrm{NANDtree}_h) = \Theta(\alpha^h)$ with $\alpha = (1+\sqrt{33})/4 = 1.68614\ldots$, taking the $k$-th root kills the hidden constant exactly and leaves $\alpha^d$. Read-once formulas are the case where randomized query complexity does compose perfectly, so $\mathrm{R}^{*} = \mathrm{R}$ here up to the constant. SaksWigderson86 Santha95
\(\deg_2(f)\) Mod-2 degree \(N\) putative Over $\mathbb{F}_2$, $\mathrm{NAND}(u,v) = 1 + uv$, so each gate multiplies its children's polynomials and the top monomial of a subtree is the product of its leaves' -- with coefficient $1$ throughout. By induction the full monomial survives: $\deg_2 = \deg = N$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\Theta(\sqrt N)\) putative At a $b$-input of an alternating read-once formula the sensitive leaves are one per gate on the levels that force $b$, giving $2^{\lceil d/2\rceil}$ on one side and $2^{\lfloor d/2\rfloor}$ on the other. The two sides therefore differ by at most $\sqrt2$ and both are $\Theta(\sqrt N)$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(\Theta(\sqrt N)\) As $\mathrm{s}^0$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(\sqrt N)\) putative A minimal certificate takes one child at every $0$-forcing gate and both children at every $1$-forcing gate (or vice versa), so it has $2^{\lceil d/2\rceil}$ or $2^{\lfloor d/2 \rfloor}$ leaves -- $\Theta(\sqrt N)$ either way. Every input of the balanced NAND tree costs the same up to $\sqrt2$: $\mathrm{C} = \Theta(\mathrm{C}_{\min})$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) The $\deg/2 = N/2$ floor is a $\mathrm{Q}_{\mathrm{E}}$ bound and does not apply here: a zero-error algorithm only forces $p_1$ to vanish on $f^{-1}(0)$, so its polynomial floor is $\mathrm{rdeg}/2 = 2^{\lceil d/2\rceil-1} = \Theta(\sqrt N)$ -- exactly the order of $\mathrm{Q}$. And the ceiling is $\mathrm{Q}_0 \le 2\mathrm{R}_0 = O(N^{0.753\ldots})$, strictly below $\mathrm{D}$: the NAND tree is one of the few places where the Las Vegas ceiling bites before the deterministic one. Contrast $\mathrm{Q}_{\mathrm{E}} = \Theta(N)$, which $\deg$ really does pin.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(O\!\big(N^{\,0.698}\big)\) Strictly below $\mathrm{R} = \Theta(N^{0.753\ldots})$, and this is the only total function for which $\mathrm{R}$ and $\mathrm{D}^{\mathrm{prod}}$ are known to be polynomially apart [Sanyal24, Thm. 1.7]. The tempting argument -- that the Saks-Wigderson lower bound is proved against an explicit product distribution, so it certifies $\mathrm{D}^{\mathrm{prod}}$ -- is wrong, and instructively so: what that distribution certifies is the zero-error cost $\overline{\mathrm{D}_0^{\mu}} = \Theta(\alpha^d)$, $\alpha = (1+\sqrt{33})/4$, and bounded error is cheaper. Knowing $\mu$, run Saks-Wigderson but recurse first on the child likelier to evaluate to $0$ rather than on a random one. Two levels down, independence gives $p_{\ell} \ge (1-\alpha_{\ell})^2$ and the recursion closes at $T(d) \le \max_{x\in[0,1]}(2-x)(1+2x-x^2)\,T(d-2) = \tfrac{2}{27}(17+7\sqrt7)\,T(d-2)$, i.e. base $\sqrt{\tfrac2{27}(17+7\sqrt7)} = 1.62207\ldots$ per level against $\alpha = 1.68614\ldots$. With $N = 2^d$ that is $N^{0.69789\ldots}$. Sanyal does not claim the exponent is tight, so no lower bound is recorded. Sanyal24
\(\mathrm{C}^0(f)\) 0-certificate complexity \(2^{\lceil d/2\rceil} = \Theta(\sqrt N)\) putative Certifying $f_d = 0$ means certifying both children to be $1$, and certifying $f_d = 1$ means certifying one child to be $0$: $\mathrm{C}^0(f_d) = 2\,\mathrm{C}^1(f_{d-1})$ and $\mathrm{C}^1(f_d) = \mathrm{C}^0(f_{d-1})$, from $\mathrm{C}^0(f_0) = \mathrm{C}^1(f_0) = 1$. So the two sides differ by exactly a factor $\sqrt2$ when $d$ is odd and agree when $d$ is even.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(2^{\lfloor d/2\rfloor} = \Theta(\sqrt N)\) putative See \(\mathrm{C}^0(f)\); the recursion swaps the two sides at every level.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(2^{\lceil d/2\rceil} = \Theta(\sqrt N)\) putative Sensitivity obeys the same recursion as certificate complexity here -- at a $0$-input every leaf that flips its own subtree is sensitive, giving $\mathrm{s}^0(f_d) = 2\,\mathrm{s}^1(f_{d-1})$, and at a $1$-input only the leaves of a single $0$-child can help, giving $\mathrm{s}^1(f_d) = \mathrm{s}^0(f_{d-1})$. So $\mathrm{s}^b = \mathrm{bs}^b = \mathrm{C}^b$ and the squeeze is tight on both sides.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(2^{\lfloor d/2\rfloor} = \Theta(\sqrt N)\) putative As \(\mathrm{bs}^0(f)\), with the sides exchanged.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(N)\) putative Non-adaptive randomness buys nothing on any function that depends on all its variables. Pick a uniformly random leaf $\ell$ and a fixed input making $\ell$ pivotal, then set $x_\ell$ uniformly at random. A non-adaptive algorithm reading $q$ positions hits $\ell$ with probability $\le q/N$, and otherwise sees a fixed string and must guess a uniform bit, so its success probability is at most $\tfrac12 + \tfrac{q}{2N}$. Hence $\mathrm{R}^{\mathrm{na}}_{1/3}(f) \ge N/3$ for every $f$ with all $N$ variables relevant, matching $\mathrm{D}^{\mathrm{na}} = N$. This is the general form of the \(\mathrm{ADDR}_k\) argument already recorded on the \(\mathrm{R}^{\mathrm{na}}(f)\) page, and it separates $\mathrm{R}^{\mathrm{na}} = \Theta(N)$ from $\mathrm{R} = \Theta(N^{0.753\ldots})$ here.
\(\mathrm{SP}(f)\) Subcube partition complexity \(N\) putative A monochromatic subcube partition writes $f$ as a sum of indicators of subcubes of codimension $\le \mathrm{SP}$, with no cancellation, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$. On a read-once formula $\deg = \mathrm{D} = N$, so all four coincide.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(N\) putative Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D} = N$; see \(\mathrm{SP}(f)\). Against $\mathrm{C} = \Theta(\sqrt N)$ this is the largest possible $\mathrm{UC}$-vs-$\mathrm{C}$ gap.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(2^{-\Theta(\sqrt N)}\) putative Writing $p_d = \Pr[f_d = 1]$ one has $p_d = 1 - p_{d-1}^2$ and $\mathrm{I}(f_d) = \prod_{j<d} 2p_j$. The map $p \mapsto 1-p^2$ has its fixed point $(\sqrt5-1)/2$ unstable, and from $p_0 = \tfrac12$ the orbit is attracted to the $2$-cycle $\{0,1\}$ with $p_{2k+2}\approx 2p_{2k}^2$, i.e. doubly exponentially. So the balanced NAND tree is, under the uniform measure, an almost constant function whose total influence decays like $2^{-\Theta(2^{d/2})}$. Numerically $\log_2 \mathrm{I}(f_d) \approx -0.145\cdot 2^{d/2}$ along even $d$. A reminder that the uniform measure is the wrong one for this function: the Saks-Wigderson product distribution is the right one.
\(\hat{L}_1(f)\) Spectral norm \(2^{\Theta(N)}\) putative Because the two subtrees are on disjoint variables, $\hat f_d(T)$ is a single product term and the spectral norm obeys the exact recursion $A_d = A_{d-1}|1-\hat f_{d-1}(\emptyset)| + \tfrac12 A_{d-1}^2$ with $\widehat{L}_1 = |\hat f_d(\emptyset)| + A_d$. The quadratic term wins, so $\log_2 \widehat{L}_1(f_d) \to 0.29396\ldots\cdot N$. Exact small values $2,\ 3.5,\ 9.265625,\ 51.6915\ldots$ for $d = 1,2,3,4$ (checked against the full Fourier expansion).
\(\mathrm{spar}(f)\) Fourier sparsity \(2^{N}\) putative Full Fourier support. Every coefficient is a product of the factors in the \(\hat{L}_1(f)\) recursion, none of which vanishes because $\Pr[f_j = 1] \notin \{0,1\}$ at every level; brute force confirms $2^N$ nonzero coefficients for $d \le 4$.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(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
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(N\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min}$. On a read-once formula $\deg = \mathrm{D} = N$, so even the cheaper side is full -- against $\mathrm{C}_{\min} = \Theta(\sqrt N)$, a quadratic $\mathrm{UC}_{\min}$-vs-$\mathrm{C}_{\min}$ gap.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(N)\) putative Pinned by $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1,\ O(\mathrm{EC}^2)\}$; $\mathrm{CG}$ is not capped by $\mathrm{D}$, but here the two ends meet anyway. Lower: $\mathrm{Adv} = \Theta(\sqrt N)$ gives $\mathrm{Adv}^2 = \Theta(N)$. Upper: $\mathrm{C}^0\mathrm{C}^1 = 2^{\lceil d/2\rceil}2^{\lfloor d/2\rfloor} = 2^d = N$. So the private-coin certificate game costs $\Theta(N)$ while the public-coin one costs $\Theta(\sqrt N)$ and $\mathrm{R}$ costs $N^{0.753\ldots}$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(N^{1/4})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(\sqrt N)$ here.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta\!\big(N^{\,0.753\ldots}\big)\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) putative Not pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(\sqrt N)$ -- star out a uniformly random one of the $\mathrm{bs}$ disjoint sensitive blocks of a maximally block-sensitive input; every unstarred bit agrees with that input, so finding a $\ast$ is unstructured search over the blocks.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) Sandwiched: $\mathrm{fbs} \le \mathrm{prt}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, i.e. between $\Theta(\sqrt N)$ and $\Theta(N^{0.753\ldots})$. Where the partition bound sits inside that window is open; the conical-junta relaxation \(\mathrm{cjdeg}_{\varepsilon}(f)\) is known to sit at the top of it.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\)· As \(\mathrm{prt}_{\varepsilon}(f)\); the relaxed bound still dominates $\mathrm{fbs}$ (the zoo's own observation that the [JainKlauck10] techniques survive dropping the completeness equality) and is still at most $\mathrm{R}$.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(2^{-\Theta(\sqrt N)}\) putative For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$; see \(\mathrm{I}(f)\).
\(\mathrm{MaxInf}(f)\) Maximum influence \(2^{-\Theta(\sqrt N)}\) putative The tree automorphisms act transitively on the leaves, so every coordinate has influence $\mathrm{I}(f)/N$; dividing the doubly exponentially small $\mathrm{I}(f) = 2^{-\Theta(\sqrt N)}$ of the \(\mathrm{I}(f)\) entry by $N$ does not change the exponent.
\(\mathrm{Var}(f)\) Variance \(2^{-\Theta(\sqrt N)}\) $4p_d(1-p_d)$ with $p_d = 1-p_{d-1}^2$ from $p_0 = \tfrac12$; the orbit escapes to the $\{0,1\}$ two-cycle doubly exponentially, as computed in the \(\mathrm{NS}_{\delta}(f)\) entry.
\(\mathrm{osss}(f)\) OSSS number \(\Theta(\sqrt N) = \Theta(2^{d/2})\) putative Both $\mathrm{Var}$ and $\mathrm{MaxInf}$ are $2^{-\Theta(\sqrt N)}$, but the ratio is clean. Write $\varepsilon_d = \min\{p_d,1-p_d\}$, so $\mathrm{Var} = 4\varepsilon_d(1-\varepsilon_d)$ and $\varepsilon_{d+2} = (2+o(1))\varepsilon_d^2$, while $\mathrm{MaxInf}(f_d) = \prod_{j<d}p_j$ picks up exactly one new small factor $\varepsilon_d$ every two levels. Hence $\mathrm{osss}(f_{d+2})/\mathrm{osss}(f_d)\to 2$. Numerically $\mathrm{osss} = 2.6,\,6.8,\,17.3,\,41,\,90,\,184$ at $d = 2,4,\dots,12$. Well below $\mathrm{R}_0 = \Theta(N^{0.753})$.
\(\mathrm{nsr}(f)\) Noise robustness \(O(\sqrt N)\) putative $\mathrm{nsr}\le 4\mathrm{I}/\mathrm{Var} = 4N/\mathrm{osss} = \Theta(\sqrt N)$ by the \(\mathrm{osss}(f)\) entry. A first-moment count suggests this is tight -- conditioned on the rare event $f = 1$, an input has $\Theta(\sqrt N)$ sensitive coordinates on average, so noise at rate $\Theta(1/\sqrt N)$ should already flip the answer -- but the matching lower bound is not recorded here.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(N\) putative The Fourier support is everything (see \(\mathrm{spar}(f)\)), so its $\mathbb{F}_2$-span is all of $\mathbb{F}_2^{N}$ and the bound $\mathrm{D}^{\oplus} \le \dim_{\mathbb{F}_2}$ is vacuous -- consistent with \(\mathrm{D}^{\oplus}(f)\) $= N$.
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(N)\) putative Between $N/4$ and $N$. Lower, by the composing Prover--Delayer bound $\mathrm{rank}(f\circ g^n) \ge \mathrm{D}(f)(\mathrm{C}_{\min}(g)-1)$: the Delayer defers the first $\mathrm{C}_{\min}(g)-1$ queries in each block, then commits to that block's value and forces it, and the game cannot end before $\mathrm{D}(f)$ blocks have reached their commitment. A single NAND gate has $\mathrm{C}_{\min} = 1$ and gives nothing, but writing $f_d = f_{d-2}\circ f_2$ with $\mathrm{C}_{\min}(f_2) = 2$ gives $\mathrm{rank} \ge 2^{d-2} = N/4$. Exact minimisation gives $1,2,3,6,11$ at $d = 1,\dots,5$. So the NAND tree has essentially full rank even though $\mathrm{C}_{\min} = \Theta(\sqrt N)$.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(N)}\) putative A rank-$r$ decision tree contains a complete binary branching of depth $r$ and so has $\ge 2^r$ leaves; with $\mathrm{rank} \ge N/4$ that is $2^{\Omega(N)}$, and $2^{\mathrm{D}} = 2^N$ is the ceiling. Exact minimisation gives $3, 7, 25, 409, 62833$ leaves at $d = 1,\dots,5$, i.e. $\log_2 \mathrm{DTsize} \approx 0.5\,N$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(\sqrt N)\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14] -- every input is critical and $f$ is the only solution function -- and $\mathrm{bs} = \Theta(\sqrt N)$. GoosPitassi14
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta\!\big(N^{\,0.753\ldots}\big)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3})$. Both directions of the recorded $\mathrm{R} = \Theta(N^{0.753\ldots})$ are in fact proved distributionally -- Saks-Wigderson's lower bound exhibits an explicit recursive $\mu$ -- so the distributional value is the same $N^{\log_2((1+\sqrt{33})/4)}$. Yao77 SaksWigderson86
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(N^{\,0.753\ldots}),\ O\!\big(N^{\,0.753\ldots}\log N\big)\) Noisy queries can only cost more than clean ones, so $\mathrm{N}_p \ge \mathrm{R}$; majority-amplifying each query of the optimal randomized tree $O(\log \mathrm{R})$ times gives $\mathrm{N}_p = O(\mathrm{R}\log \mathrm{R})$ [FRPU94]. FRPU94
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(\sqrt N),\ O(\sqrt N\log N)\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt N)$, and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ in general [BNRdW05]. Whether the logarithm can be removed for the NAND tree is open; it can be for \(\oplus_n\). BNRdW05
\(\chi(f)\) Conflict complexity \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) $\chi = \Omega(\mathrm{bs}) = \Omega(\sqrt N)$ [Li18], and $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) Above $\chi = \Omega(\mathrm{bs})$ and above the recorded $\mathrm{RS} = \Omega(\sqrt N)$; below $\mathrm{LR} \le \mathrm{R} = O(N^{0.753\ldots})$ [GLSS19]. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R}$ [BBGM22] gives $\Omega(N^{0.377})$, which the stronger $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(\sqrt N)$ improves. Note that $\mathrm{R}$ is multiplicative along this family ($f_d\circ f_e = f_{d+e}$), so the composition theorem $\mathrm{R}(F\circ f_d^m) = \Omega(\mathrm{R}(F)\mathrm{LR}(f_d))$ is tight for these gadgets only if $\mathrm{LR}$ sits at the top of this window. BBGM22
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(2^{-\Theta(\sqrt N)}\) putative For constant $\delta$, $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$, since every factor $1-(1-2\delta)^{|S|}$ with $|S|\ge 1$ lies in $[2\delta,1]$. The uniform bias satisfies $p_d = 1-p_{d-1}^2$ from $p_0 = 1/2$, which oscillates and escapes: $p_{2m} \approx 2p_{2m-2}^2$, so $\min\{p_d, 1-p_d\} = 2^{-\Theta(2^{d/2})} = 2^{-\Theta(\sqrt N)}$ and $\mathrm{Var} = 2^{-\Theta(\sqrt N)}$. This is the same doubly exponential collapse that produces the recorded $\mathrm{I}(f) = 2^{-\Theta(\sqrt N)}$. ODonnell14
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - 2^{-\Theta(\sqrt N)}\) putative From $\mathrm{Stab}_\rho = 1-2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: at any constant noise rate the tree is essentially constant, so it is almost perfectly stable.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(2^{\lfloor d/2\rfloor} = \Theta(\sqrt N)\) putative Write $f_d = \mathrm{OR}_2(\overline{f_{d-1}},\overline{f_{d-1}})$ and $\overline{f_d} = \mathrm{AND}_2(f_{d-1},f_{d-1})$, and set $a_d = \mathrm{ndeg}(f_d)$, $b_d = \mathrm{ndeg}(\overline{f_d})$. Nondeterministic degree is exactly multiplicative over the disjoint blocks of an $\mathrm{AND}$ [IJKKKSWW23], so $b_d = 2a_{d-1}$. For the $\mathrm{OR}$ level: restricting one block to a $0$-input of $\overline{f_{d-1}}$ gives $a_d \ge b_{d-1}$, while $a_d \le \mathrm{C}^1(f_d) = \mathrm{C}^0(f_{d-1}) = 2^{\lceil (d-1)/2\rceil} = 2^{\lfloor d/2\rfloor}$ (sum the indicators of the $1$-certificates -- all coefficients positive, so no cancellation). With $a_0 = b_0 = 1$ and $a_1 = 1$ (witness $1+x_1-2x_2$ for $\mathrm{NAND}_2$) the two ends meet and $a_d = 2^{\lfloor d/2\rfloor}$ exactly, matching the recorded $\mathrm{C}^1$. IJKKKSWW23
\(\mathrm{rdeg}(f)\) Rational degree \(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
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(2^{\lfloor d/2\rfloor - 1} = \Theta(\sqrt N)\) putative $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ [deWolf03], and $\mathrm{ndeg}(f_d) = 2^{\lfloor d/2\rfloor}$ from the \(\mathrm{ndeg}(f)\) entry. Nondeterministic quantum queries therefore buy nothing over bounded-error quantum queries on the NAND tree, both being $\Theta(\sqrt N)$. deWolf03
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(O(\sqrt N)\) One-sided approximate degree is squeezed by $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = \Theta(\sqrt N)$; no lower bound better than the trivial one is known, since the threshold degree of the balanced NAND tree is not pinned down.
\(\mathrm{sdeg}(f)\) Sign degree \(O(\sqrt N)\) From $\mathrm{sdeg} \le \widetilde{\deg} = \Theta(\sqrt N)$. Minsky-Papert-style lower bounds give nothing here: each gate has fan-in $2$, so the $\Omega(\min\{m,\sqrt b\})$ bound for $\mathrm{AND}_m\circ\mathrm{OR}_b$ degenerates to $\Omega(1)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(\sqrt N)\) At most both $\mathrm{rdeg} = \Theta(\sqrt N)$ and $\widetilde{\deg} = \Theta(\sqrt N)$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(\sqrt N)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) \le O(\mathrm{rdeg}) = O(\sqrt N)$ [MahadevdeWolf15]. Since $\mathrm{Q} = \Theta(\sqrt N)$ already, post-selection can save at most a constant factor unless $\mathrm{rdeg}_{1/3} \ll \mathrm{rdeg}$ here. MahadevdeWolf15
\(\deg_p(f)\) Mod-p degree \(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$.

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 135 in total, strongest first.

… and 121 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

Cited as a witness by

Notes

The Saks-Wigderson conjecture -- that $\mathrm{D}(f) = O(\mathrm{R}_0(f)^{1.33})$ for all total $f$, i.e. that this function is extremal -- was refuted by [ABBLSS17], who pushed the exponent to $2$ (which is optimal).