Q The Query Complexity Zoo
\(\mathrm{MP}_m\)

Minsky-Papert one-in-a-box

The unbalanced AND-OR tree, tuned so that Minsky-Papert's $\min\{m,\sqrt b\}$ is maximised: $\mathrm{sdeg} = \Theta(N^{1/3})$.

total composed arity: $N = m^3$ bits: $m$ blocks of $m^2$— also: one-in-a-box, AND_m o OR_{m^2}, the unbalanced AND-OR tree

Description

$\mathrm{MP}_m = \mathrm{AND}_m \circ \mathrm{OR}_{m^2}$: split $N = m^3$ bits into $m$ boxes of $m^2$, and accept iff every box contains a $1$.

This is not the balanced \(\mathrm{AND}_n \circ \mathrm{OR}_n\). The shape matters: Minsky and Papert's theorem is $\mathrm{sdeg}(\mathrm{AND}_m\circ\mathrm{OR}_b) = \Omega(\min\{m,\sqrt b\})$, and $b = m^2$ is the choice that makes both terms equal. Quoting $\Theta(N^{1/3})$ for the balanced tree is a common slip.

Formal definition

$$\mathrm{MP}_m(x) = \bigwedge_{j=1}^{m}\ \bigvee_{i=1}^{m^2} x^j_i, \qquad N = m^3.$$

Measure values

MeasureValueNotes
\(\mathrm{sdeg}(f)\) Sign degree \(\Theta(m) = \Theta(N^{1/3})\) The original theorem, and the first threshold-degree lower bound ever proved: no polynomial of degree $o(m)$ sign-represents $\mathrm{MP}_m$. Upper bound $O(m)$: the symmetrisation argument is tight here. MinskyPapert69
\(\mathrm{D}(f)\) Deterministic query complexity \(N = m^3\) Read-once AND-OR formulas are evasive.
\(\deg(f)\) Exact degree \(N = m^3\) Degree is multiplicative for block composition, and $\deg(\mathrm{AND}_m)\deg(\mathrm{OR}_{m^2}) = m\cdot m^2$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(m^3) = \Theta(N)\) The zoo's own \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) entry records $\mathrm{R}(f)=\Theta(n)\Rightarrow\mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ [CKMPSS23], and the recorded $\mathrm{R}$ is linear in the arity here -- the AND-OR tree is evasive even for randomised algorithms. CKMPSS23
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(m^3) = \Theta(N)\) Randomised evaluation of a depth-two AND-OR tree with fan-ins $m$ and $m^2$ costs $\Theta(m\cdot m^2)$. SaksWigderson86 Snir85
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) The same $\Theta(\sqrt{mb})$ that gives \(\mathrm{AND}_n \circ \mathrm{OR}_n\) its $\Theta(\sqrt N)$; here $\sqrt{m\cdot m^2} = m^{3/2}$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) Robust quantum search on the two levels; matches $\widetilde{\deg}/2$. HoyerMoscadeWolf03
\(\mathrm{s}(f)\) Sensitivity \(m^2 = N^{2/3}\) One-sided. At a $1$-input only a box's unique $1$ is sensitive, so $\mathrm{s}^1 = m$; at a $0$-input with exactly one empty box, every one of that box's $m^2$ bits is sensitive, so $\mathrm{s}^0 = m^2$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(m\) As above.
\(\mathrm{s}^0(f)\) 0-sensitivity \(m^2\) As above.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(\sqrt N)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(m^{3/2}) = \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(m^{3/2}) = \Theta(\sqrt N)$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(m^3) = \Theta(N)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and $\mathrm{R}_{\varepsilon}(f) = \Theta(m^3) = \Theta(N)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(m^{3/2}) = \Theta(\sqrt N)$ here.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(N = m^3\) Sandwiched exactly: $\deg(f) \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, and both ends are $N = m^3$ here. Exact quantum computation buys nothing on a read-once AND-OR formula, while bounded error buys the full quadratic $\Theta(\sqrt N)$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(m\) A $1$-certificate names one $1$ in each of the $m$ boxes.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(m^2 = N^{2/3}\) A $0$-certificate must exhibit an entirely empty box, and a box has $m^2$ bits. This is the asymmetry the whole function is built on.
\(\mathrm{C}(f)\) Certificate complexity \(m^2 = N^{2/3}\) $\max\{\mathrm{C}^0,\mathrm{C}^1\}$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(m\) At a $1$-input with exactly one $1$ per box, the $m$ singleton blocks are minimal and disjoint.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(m^2 = N^{2/3}\) At a $0$-input with exactly one empty box, flipping any single bit of that box already makes the function $1$: $m^2$ disjoint singleton blocks.
\(\mathrm{bs}(f)\) Block sensitivity \(m^2 = N^{2/3}\) From $\mathrm{bs}^0$. Together with $\mathrm{D} = N = m^3$ this is a cube-root gap, the largest a read-once formula allows.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(m^2) = \Theta(N^{2/3})\) Squeezed between $\mathrm{bs} = m^2$ and $\mathrm{C} = m^2$.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(m^2) = \Theta(N^{2/3})\) $\mathrm{RC} = \Theta(\mathrm{fbs})$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(m^3) = \Theta(N)\) Squeezed between $\mathrm{R} = \Theta(N)$ and $\mathrm{D} = N$.
\(\lambda(f)\) Spectral sensitivity \(m^{3/2} = \sqrt N\) $\lambda$ is exactly multiplicative under block composition [ABKRT21], so $\lambda(\mathrm{AND}_m \circ \mathrm{OR}_{m^2}) = \sqrt m \cdot \sqrt{m^2} = m^{3/2}$. This matches $\mathrm{Q} = \Theta(\sqrt N)$ up to a constant -- spectral sensitivity is tight here, while it is a $\sqrt{\ }$-factor loose against $\mathrm{s} = m^2$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(m = N^{1/3}\) putative Every $1$-input costs exactly $m$ (one witness per box) and every $0$-input costs exactly $m^2$ (a whole empty box), so the minimum is the $1$-side: $\mathrm{C}_{\min} = m$ against $\mathrm{C} = m^2$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(N = m^3\) Every variable is relevant.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(m^3) = \Theta(N)\) Between $\mathrm{R} = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}} = N$.
\(\deg_2(f)\) Mod-2 degree \(N = m^3\) putative As for any read-once AND-OR formula: over $\mathbb{F}_2$, $\bigvee_i x_i = 1 + \prod_i(1+x_i)$ contributes the full monomial of its box with coefficient $1$, and the outer AND multiplies the boxes.
\(\mathrm{SP}(f)\) Subcube partition complexity \(N = m^3\) putative A partition of the cube into monochromatic subcubes writes $f$ as a sum of indicators of conjunctions of $\le \mathrm{SP}$ literals with no cancellation, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg = \mathrm{D} = N$, so the chain collapses. Read-once formulas are always pinned this way.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(N = m^3\) putative Pinned by the same $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$ collapse; see \(\mathrm{SP}(f)\). A second, self-contained proof: $|f^{-1}(1)| = (2^{m^2}-1)^m$ is odd, and an unambiguous $1$-certificate family partitions $f^{-1}(1)$ into subcubes of sizes that are powers of two, so one of them must be a single point -- a certificate of full width $N$. Against $\mathrm{C} = m^2$ this is a $\mathrm{UC}$-vs-$\mathrm{C}$ gap of $N^{1/3}$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(m^2) = \Theta(N^{2/3})\) Squeezed between $\mathrm{fbs} = \Theta(m^2)$ and $\mathrm{C} = m^2$.
\(\mathrm{rank}(f)\) Decision tree rank \(m = N^{1/3}\) putative Upper: read the boxes in order, and inside a box read bits until a $1$ appears. A box subtree is a caterpillar, of rank $1$, and grafting a rank-$r$ tree onto the leaves of a rank-$1$ tree gives rank $\le r+1$, so the rank climbs by exactly one per box. Lower: a Delayer who always defers survives $\mathrm{C}_{\min} = m$ rounds. So $\mathrm{rank} = m$ against $\mathrm{D} = m^3$ -- almost all of the depth is caterpillar, and it lives inside the boxes.
\(\mathrm{DTsize}(f)\) Decision tree size \(\Theta(m^{2m})\) putative The tree above has $L_k = m^2 L_{k-1} + 1$ leaves after $k$ boxes, i.e. $\sum_{j=0}^{m} m^{2j}$ leaves. Matching lower bound: the $m^{2m}$ inputs with exactly one $1$ per box reach pairwise distinct leaves, since a monochromatic-$1$ subcube containing two of them would leave both witnesses of some box free and hence contain an input with that box empty. So $m^{2m} \le \mathrm{D}_{\mathrm{size}} < m^{2m}(1 + 2m^{-2})$. Verified by exhaustive search at $(m,\,\text{box size}) = (2,4)$, where both sides give $21$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(m^2 = N^{2/3}\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)); here $\mathrm{bs} = m^2$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(m^3) = \Theta(N)\) For a Boolean function the canonical answer is forced, so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)); here $\mathrm{R} = \Theta(N)$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(m^3) = \Theta(N)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(N)$. Yao77
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(m^2) = \Theta(N^{2/3})\) $\mathrm{FC} = \mathrm{fbs}$ exactly, by LP duality, and $\mathrm{fbs} = \Theta(m^2)$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(m^3) = \Theta(N)\) Sandwiched: $\mathrm{R}(f) \le \mathrm{R}^{1}(f) \le \mathrm{R}_{0}(f)$, with both ends $\Theta(m^3) = \Theta(N)$ here.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(m^3) = \Theta(N)\) Lower: sabotage complexity composes perfectly, $\mathrm{RS}(f\circ g) \ge \mathrm{RS}(f)\mathrm{RS}(g)$ [BenDavidKothari18], and a sabotaged $\mathrm{AND}_k$ or $\mathrm{OR}_k$ with a single $\ast$ needs $\Theta(k)$ queries to locate it, so $\mathrm{RS} \ge \mathrm{RS}(\mathrm{AND}_m)\mathrm{RS}(\mathrm{OR}_{m^2}) = \Omega(m^3)$. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(m^3)$. Note this is a full $\mathrm{N}^{1/3}$ above $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(m^2)$. BenDavidKothari18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(m^3) = \Theta(N)\) Sandwiched: $\bar\chi(g) = \Omega(\mathrm{RS}(g))$ and $\bar\chi \le \mathrm{LR} \le \mathrm{R}$, with $\mathrm{RS} = \Theta(m^3) = \mathrm{R}$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(m^3) = \Theta(N)\) Sandwiched between $\bar\chi = \Theta(m^3)$ and $\mathrm{R} = \Theta(m^3)$. The inner composition measure loses nothing on a read-once AND-OR tree.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(m^3) = \Theta(N)\) Sandwiched: $\mathrm{R}^{*}(f) = \Omega(\mathrm{LR}(f))$ and $\mathrm{R}^{*}(f) \le \mathrm{R}(f)$, with both ends $\Theta(m^3)$ here. So iterating $\mathrm{MP}$ costs the full $\mathrm{R}$ per level.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(m^2) = \Theta(N^{2/3})\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ [ABIKPS17], and $\mathrm{fbs} = \Theta(m^2)$ here. A cube-root below $\mathrm{R} = \Theta(N)$: the classical adversary is far from tight on the one-in-a-box function. ABIKPS17
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(m^2) = \Theta(N^{2/3})\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ for every $f$ [CGLMSG23], and $\mathrm{CA} = \Theta(m^2)$ here. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(m^2) = \Theta(N^{2/3})\) 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)\)). CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(m^2) = \Theta(N^{2/3})\) The same non-signaling collapse; see \(\mathrm{CG}^{*}(f)\). CGLMSG23
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(m^3) = \Theta(N)\) Pinned by the total-function sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23]: the bottom is $\mathrm{Adv}^2 = \Theta(m^3)$ (equally $\mathrm{R}_0 = \Theta(m^3)$) and the top is $\mathrm{C}^0\mathrm{C}^1 = m^2\cdot m = m^3$. So the private-coin game costs the full $\mathrm{D}$ here, a whole $N^{1/3}$ above the public-coin value $\Theta(m^2)$ -- the largest separation between the two variants that the $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ ceiling permits on this function. CGLMSG23
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(N = m^3\) putative The parity argument recorded for \(\mathrm{UC}(f)\) works on both sides, so the one-sided relaxation buys nothing. $|f^{-1}(1)| = (2^{m^2}-1)^m$ is odd, and $|f^{-1}(0)| = 2^{N} - (2^{m^2}-1)^m$ is even minus odd, hence also odd. An unambiguous $b$-certificate family partitions $f^{-1}(b)$ into subcubes of sizes $2^{N-w_i}$; an odd total forces some $w_i = N$. So $\mathrm{UC}^0 = \mathrm{UC}^1 = N$ and $\mathrm{UC}_{\min} = N = m^3$, against $\mathrm{C} = m^2$. This is an extreme point of $\mathrm{C} \ge \mathrm{UC}_{\min}^{1.22}$-type separations in the opposite direction: here $\mathrm{UC}_{\min}$ is as far above $\mathrm{C}$ as $\mathrm{D} \le \mathrm{UC}_{\min}^2$ allows it to be useful at all.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Theta(m) = \Theta(N^{1/3})\) putative A full $\sqrt m$ below $\widetilde{\deg} = \Theta(m^{3/2})$: dropping the upper constraint on the $1$-inputs is worth a quadratic saving here. Upper: $p(x) = \prod_{j=1}^{m}\big(\sum_{i} x^j_i\big)$ has degree $m$, vanishes whenever some box is empty, and is $\ge 1$ when every box has a $1$ -- exactly a one-sided approximation. Lower: $\mathrm{sdeg}(f) \le \widetilde{\deg}_+(f)$ (\(\mathrm{sdeg}(f)\) vs \(\widetilde{\deg}_{+}(f)\)) and $\mathrm{sdeg} = \Theta(m)$ by [MinskyPapert69]. Note this makes $\mathrm{MP}$ a clean witness that one-sided approximate degree is not $\Theta(\widetilde{\deg})$; compare \(\mathrm{AND}_n\), where the two coincide. MinskyPapert69
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Omega(m^3/\log m),\ O(m^3)\)· putative Lower: take each leaf independently $1$ with probability $p$ chosen so that each $\mathrm{OR}_{m^2}$ is $0$ with probability $q = \ln 2/m$, i.e. $p = \Theta(\log m / m^2)$; then $\mathrm{AND}$ is $1$ with probability $\tfrac12$, so the answer is balanced. Resolving one box costs $\approx 1/p = \Theta(m^2/\log m)$ queries in expectation, and leaving $t$ boxes unresolved leaves error $\approx tq$, so at least $m/2$ boxes must be resolved: $\mathrm{D}^{\mu} = \Omega(m^3/\log m)$. Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(m^3)$. The log is probably real and cannot be argued away by the tempting route -- the classical $\Omega(mb)$ lower bound is proved against a correlated distribution (one planted $1$ per box), not a product one, and \(\bar{\wedge}\text{-tree}\) shows that at growing depth the analogous gap is not a log but a polynomial [Sanyal24]. At depth $2$ the saving compounds only once, which is why it stays logarithmic here. Sanyal24
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Omega(m^2),\ O(m^3)\) Sandwiched, and the sandwich is loose. Lower: $\mathrm{RC} \le \mathrm{prt}_{\varepsilon}$ (\(\mathrm{RC}(f)\) vs \(\mathrm{prt}_{\varepsilon}(f)\)) with $\mathrm{RC} = \Theta(m^2)$; the $\widetilde{\deg} \le \mathrm{prt}$ route is weaker here, $\Omega(m^{3/2})$. Upper: $\mathrm{prt}_{\varepsilon} \le \mathrm{R} = \Theta(m^3)$. Whether the partition bound is tight for $\mathrm{R}$ is open in general, and the AND-OR tree is exactly the shape where nobody has closed it.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Omega(m^2),\ O(m^3)\) The same window as \(\mathrm{prt}_{\varepsilon}(f)\), and it cannot be narrower: $\mathrm{RC} \le \overline{\mathrm{prt}}_{\varepsilon} \le \mathrm{prt}_{\varepsilon} \le \mathrm{R}$, with $\mathrm{RC} = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^3)$.
\(\chi(f)\) Conflict complexity \(\Omega(m^2),\ O(m^3)\) Sandwiched: $\chi(g) = \Omega(\mathrm{bs}(g))$ (\(\chi(f)\) vs \(\mathrm{bs}(f)\)) gives $\Omega(m^2)$ -- the $\mathrm{R} = O(\chi^2)$ route only gives $\Omega(m^{3/2})$ -- and $\chi \le \bar\chi = \Theta(m^3)$ (\(\chi(f)\) vs \(\bar{\chi}(f)\)). The gap here is exactly the gap between $\mathrm{bs}$ and $\mathrm{R}$ on a read-once AND-OR tree, which is why $\mathrm{MP}$ is a natural test case for whether conflict complexity is $\Theta(\bar\chi)$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega(m^{3/2}),\ O(m^3)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$ (\(\widetilde{\deg}_{\varepsilon}(f)\) vs \(\mathrm{cjdeg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg} = \Theta(m^{3/2})$ and $\mathrm{R} = \Theta(m^3)$. On the balanced \(\bar{\wedge}\text{-tree}\) the upper end is known to be attained; here it is open which end is the truth.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(\Omega(m),\ O(m^{3/2})\) Lower: a rational $1/3$-approximation $p/q$ makes $(p - q/2)\,q$ a sign-representing polynomial of degree $\le 2\,\mathrm{rdeg}_{\varepsilon}$, so $\mathrm{rdeg}_{\varepsilon}(f) \ge \mathrm{sdeg}(f)/2 = \Omega(m)$ by [MinskyPapert69]. Upper: $\mathrm{rdeg}_{\varepsilon} \le \widetilde{\deg} = O(m^{3/2})$. Rational approximation famously does not compose -- the outer rational function is evaluated at perturbed inputs where its denominator can vanish -- so the $O(\log)$ rational approximations of the individual $\mathrm{AND}$ and $\mathrm{OR}$ gates give nothing for the tree. MinskyPapert69
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Omega(m),\ O(m^{3/2})\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15], and the approximate rational degree sits in $[\Omega(m), O(m^{3/2})]$ here; see \(\mathrm{rdeg}_{\varepsilon}(f)\). So it is open whether post-selection beats plain quantum on the one-in-a-box function, and the whole question is the constant-vs-$\sqrt m$ gap in that window. MahadevdeWolf15
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(m) = \Theta(N^{1/3})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m^2)$ here. Curiously this coincides with $\mathrm{sdeg}$ and with $\mathrm{C}_{\min}$, all three at $N^{1/3}$. Aaronson08
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(m^2),\ O(m^3)\) putative Lower: planting a $1$ in every box but one restricts $f$ to $\mathrm{OR}_{m^2}$, and zero-error quantum search has no speedup at all, $\mathrm{Q}_0(\mathrm{OR}_b) = b$ [BCWZ99]. Upper: $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} = N$. The gap is genuine -- the zoo does not know whether zero-error costs the full $\Theta(N)$ here, though $\mathrm{Q} = \Theta(N^{1/2})$ shows bounded error does not. BCWZ99
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(m^3/2^{m^2})\) putative A bit of box $j$ is sensitive exactly when the other $m^2-1$ bits of its box are $0$ and every other box contains a $1$, so $\mathrm{I}(f) = m\cdot m^2\cdot 2^{-(m^2-1)}(1-2^{-m^2})^{m-1}$. Almost all of the cube is a $0$-input with two or more empty boxes, where nothing is sensitive at all, so the average sensitivity is exponentially far below $\mathrm{s} = m^2$. Checked exactly at box size $4$ with $2$ boxes.
\(\hat{L}_1(f)\) Spectral norm \(\Theta(2^m) = 2^{\Theta(N^{1/3})}\) putative Writing $f$ in the $\pm1$ encoding, $F = 1 - 2^{1-m}\prod_{j}(1 - G_j)$ with $G_j$ the $\pm1$ form of $\mathrm{OR}_{m^2}$; the boxes are disjoint so the norms multiply, giving exactly $\hat L_1(F) = |1 - 2(1-2^{-m^2})^m| + 2(2^m-1)(1-2^{-m^2})^m = (1+o(1))\,2^{m+1}$. Checked exactly at box size $4$ with $2$ boxes ($6.03125$).
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(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.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(N = m^3\) Between $\mathrm{D}^{\oplus} = N$ and the arity $N$, since $\mathrm{D}^{\oplus}(f) \le \dim_{\mathbb{F}_2}(f) \le n$.
\(\mathrm{spar}(f)\) Fourier sparsity \(2^{N} = 2^{m^3}\) putative Full: no Fourier coefficient vanishes. The boxes are disjoint, so $\hat f(S) = \prod_j \hat g_j(S_j)$ where $g_j$ is the box $\mathrm{OR}_{m^2}$, and every coefficient of $\mathrm{OR}_k$ is nonzero ($1-2^{-k}$ on the empty set, $-2^{-k}$ elsewhere). Together with $\mathrm{L}_1 = \Theta(2^{m})$ this puts MP at the opposite corner from \(\mathrm{SINK}_m\): maximal sparsity, tiny spectral norm.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(m^3 2^{-m^2})\) For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f)$.
\(\mathrm{MaxInf}(f)\) Maximum influence \(\Theta(2^{-m^2})\) putative All $N$ coordinates are equivalent under the symmetry group, so $\mathrm{MaxInf} = \mathrm{I}(f)/N = 2^{1-m^2}(1-2^{-m^2})^{m-1}$. Exponentially small, yet $\mathrm{D} = N$ -- MP is a stress test for OSSS-type bounds, which only give $\mathrm{D} \ge \mathrm{Var}/\mathrm{MaxInf}$ with $\mathrm{Var}$ itself exponentially small.
\(\mathrm{Var}(f)\) Variance \((4+o(1))\,m\,2^{-m^2}\) $2\,\mathrm{NS}_{1/2}$ from the \(\mathrm{NS}_{\delta}(f)\) entry; almost every input is a $1$-input, and $1-p = (1+o(1))m2^{-m^2}$ is the chance that some box is empty.
\(\mathrm{osss}(f)\) OSSS number \(\Theta(m) = \Theta(N^{1/3})\) putative $\Theta(m2^{-m^2})$ over $\Theta(2^{-m^2})$: the two exponentially small quantities cancel and leave the number of boxes. Cubically short of $\mathrm{D} = N = m^3$.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(m^2) = \Theta(N^{2/3})\) putative $\mathrm{NS}_\delta = (2+o(1))m2^{-m^2}(1-(1-\delta)^{m^2})$ crosses $\mathrm{Var}/4$ at $(1-\delta)^{m^2} = \tfrac12$, so $\delta^{*} = \Theta(1/m^2)$: the answer changes when the one nearly-empty box loses its last element. Tight against $\mathrm{s} = m^2$, and $\mathrm{osss}\cdot\mathrm{nsr} = \Theta(N)$ -- the two normalizations split the $\mathrm{AND}\circ\mathrm{OR}$ tree between its two levels.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \((2+o(1))\,m\,2^{-m^2}\big(1-(1-\delta)^{m^2}\big)\) putative Almost every input is a $1$-input; noise flips the answer essentially only by emptying the one box that was a singleton away from empty. Exactly, $\mathrm{NS}_\delta = \tfrac12(1-\mathrm{Stab}_{1-2\delta})$ with the $\mathrm{Stab}$ below. Consistency check: as $\delta \to 0$ this is $\delta\cdot 2m^3 2^{-m^2} = (1+o(1))\,\delta\,\mathrm{I}(f)$, matching $\mathrm{NS}_\delta \approx \delta\,\mathrm{I}$.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - (4+o(1))\,m\,2^{-m^2}\big(1-(\tfrac{1+\rho}{2})^{m^2}\big)\) putative Exactly $1 - 4\mu + 4\nu^{m}$ with $\mu = (1-2^{-m^2})^{m}$ and $\nu = 1 - 2^{1-m^2} + (\tfrac{1+\rho}{4})^{m^2}$, since the boxes are independent and a $\rho$-correlated pair keeps a given box empty with probability $(\tfrac{1+\rho}{4})^{m^2}$. Checks: $\rho = 1$ gives $1$, and $\rho = 0$ gives $(1-2\mu)^2 = \mathbb{E}[F]^2$. Unlike \(\mathrm{IP}_n\), MP is almost perfectly noise-stable, because it is almost constant.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(m = N^{1/3}\) putative Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = m$. Lower: planting a $0$ in all but one bit of each box restricts MP to $\mathrm{AND}_m$, and a polynomial nonzero exactly at $1^m$ must be a multiple of $\prod_i x_i$, so $\mathrm{ndeg}(\mathrm{AND}_m) = m$; restrictions do not increase $\mathrm{ndeg}$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\lceil m/2 \rceil = \Theta(N^{1/3})\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ [deWolf03], and $\mathrm{ndeg} = m$ here. deWolf03
\(\mathrm{rdeg}(f)\) Rational degree \(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$.
\(\deg_p(f)\) Mod-p degree \(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.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$, with $\lambda = m^{3/2}$ and $\mathrm{Q} = \Theta(m^{3/2})$. The positive-weights adversary is tight here, and sits exactly at its certificate barrier $\sqrt{\mathrm{C}^0\mathrm{C}^1} = \sqrt{m^2\cdot m} = m^{3/2}$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(m^{3/2}) = \Theta(\sqrt N)\)· Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(m^{3/2})$. Upper: the $O(\sqrt N)$ algorithm for a two-level AND-OR tree is robust quantum search [HoyerMoscadeWolf03] -- that is exactly the point of the technique -- so noise costs only a constant factor and no $\log$. HoyerMoscadeWolf03
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(m^3),\ O(m^3\log m)\) Between $\mathrm{R} = \Theta(m^3)$ and $O(\mathrm{R}\log \mathrm{R})$. The influence-based lower bound $\mathrm{N}_p = \Omega(\mathrm{I}\log \mathrm{I})$ [GLX26noisy] is useless here, $\mathrm{I}$ being exponentially small, so the zoo does not know whether the $\log$ is needed -- in sharp contrast to \(\mathrm{IP}_n\) and \(\oplus_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. 15 in total, strongest first.

… and 1 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

Minsky and Papert introduced this function in Perceptrons (1969) to show that a perceptron over degree-$k$ monomials cannot compute it unless $k = \Omega(N^{1/3})$ -- the first lower bound on threshold degree, and still the template for the dual-polynomial arguments used on \(\mathrm{SURJ}_{N,R}\) and $\mathrm{AC}^0$.