Ambainis' exact-quantum function
The first total function with a superlinear exact quantum speedup: $\mathrm{Q}_E = O(\mathrm{D}^{0.8675})$.
total
arity: $3^d$ bits— also: iterated NOT-ALL-EQUAL, NE^d
Description
The $d$-fold iteration of the $3$-bit NOT-ALL-EQUAL gadget $\mathrm{NE}(x_1,x_2,x_3) = 1$ unless $x_1=x_2=x_3$. Iterating means substituting a fresh copy of $\mathrm{NE}^{d-1}$ for each of the three inputs, so $\mathrm{NE}^d$ is a read-once formula on $3^d$ bits.
Formal definition
$\mathrm{NE} = \mathrm{OR}(x_1\oplus x_2,\ x_2\oplus x_3)$, of degree $2$ but deterministic complexity $3$, and both behave multiplicatively under iteration: $\mathrm{D}(\mathrm{NE}^d)=3^d$ and $\deg(\mathrm{NE}^d)=2^d$ [NS94]. The exact quantum algorithm of [Ambainis13] is built inductively: it maintains a designated basis state whose amplitude is $1$ on $0$-inputs and a fixed $\alpha<1$ on $1$-inputs, and interleaves the induction steps (which push $\alpha$ towards $1$) with amplitude amplification (which pushes it back), finishing with one more amplification that separates the two cases perfectly.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{D}(f)\) Deterministic query complexity | \(3^d\) | Exactly the input length. $\mathrm{NE}^d(0,\dots,0)=0$ while every weight-one input evaluates to $1$, so all $3^d$ variables are sensitive there. NS94 Ambainis13 |
| \(\mathrm{s}(f)\) Sensitivity | \(3^d\) | Same all-zero input: $\mathrm{s}_0 = 3^d$, and $\mathrm{s}\le n = 3^d$. This is what forces $\mathrm{D}$ and $\mathrm{R}$ to be maximal. Ambainis13 |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(3^d\) | Squeeze: the all-zero input is fully sensitive, and $\mathrm{s}_0\le n$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(3^d\) | Squeeze: $\mathrm{s}\le\mathrm{bs}\le n$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(3^d\) | Squeeze: $\mathrm{s}_0\le\mathrm{bs}_0\le n$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(3^d\) | Squeeze: $\mathrm{bs}\le\mathrm{fbs}\le n$. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(3^d\) | Squeeze: $\mathrm{fbs}\le\mathrm{RC}\le\mathrm{D}$. |
| \(\mathrm{C}(f)\) Certificate complexity | \(3^d\) | Squeeze: $\mathrm{bs}\le\mathrm{C}\le n$. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(3^d\) | Squeeze: $\mathrm{bs}_0\le\mathrm{C}_0\le n$. Certifying the all-zero input really does require all $3^d$ bits. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(3^d\) | Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(3^d\) | Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(3^d\) | Squeeze: $\mathrm{D}\le\mathrm{Dna}\le n$. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(3^d\) | The all-zero input has full sensitivity, so $\mathrm{R}=\Omega(\mathrm{s})=\Omega(3^d)$; and $\mathrm{R}\le\mathrm{D}=3^d$. So the exact quantum speedup below is a speedup over bounded-error randomized query complexity too. Ambainis13 |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(3^d\) | 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 all-zero input has full sensitivity. CKMPSS23 |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(3^d\) | Squeeze: $\mathrm{R}\le\mathrm{R}_0\le\mathrm{D}$. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(3^d\) | Squeeze: $\mathrm{R}\le\mathrm{Rna}\le\mathrm{Dna}$. |
| \(\deg(f)\) Exact degree | \(2^d\) | $\deg(\mathrm{NE})=2$ and degree is multiplicative for iterated read-once composition, so $\deg = 2^d = n^{\log_3 2} = n^{0.6309\ldots}$. The gap $\mathrm{D}=\deg^{\log_2 3}$ is what makes an exact quantum speedup possible at all: $\mathrm{Q}_E\ge\deg/2$, so a function with $\mathrm{D}=\Theta(\deg)$ can never show one. NS94 |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(2.1213^d)\) | The bounded-error complexity is $\Theta((3/\sqrt2)^d) = \Theta(n^{0.6845\ldots})$: the lower bound is Ambainis' adversary argument and the matching upper bound follows from the optimality of the negative-weight adversary bound. Note this is above $\deg$, so the degree lower bound on $\mathrm{Q}$ is not tight here. Ambainis13 |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(3^d\) | Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(3^d)\) | Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(3^d)\) | Squeeze: $\mathrm{CG}^{\mathrm{pub}}=\Theta(\mathrm{CA})$. |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(3^d)\) | Squeeze: the non-signaling, entangled and public-coin certificate games all collapse to $\Theta(\mathrm{CA})$. |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(3^d)\) | Squeeze: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CG}^{\mathrm{pub}})=\Theta(\mathrm{CA})$. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Omega(3^d)\) | Squeeze: $\mathrm{CG}\ge\mathrm{CG}^{\mathrm{pub}}=\Theta(3^d)$, equally $\mathrm{R}_0=O(\mathrm{CG})$. Only a lower bound is recorded: the ceiling available is $\mathrm{CG}\le\mathrm{C}^0\mathrm{C}^1=\Theta(9^d)$ (or $\mathrm{CG}=O(\mathrm{EC}^2)$, the same), and private randomness is not bounded by $\mathrm{R}_0$ -- $\mathrm{CG}(\oplus_n)=\Theta(n^2)$ while $\mathrm{R}_0(\oplus_n)=n$. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\Theta(3^d)\) | Squeeze: $\mathrm{FC}\le\mathrm{EC}\le\mathrm{C}$, and both ends are $3^d$. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(3^d)\) | Squeezed between $\mathrm{RC}$ and $2\mathrm{R}$ [JainKlauck10], which coincide at $3^d$. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(3^d)\) | Squeeze: $\overline{\mathrm{prt}}\ge\mathrm{RC}=3^d$ and $\overline{\mathrm{prt}}\le\mathrm{prt}$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(3^d\) putative | The inequality runs $\mathrm{R}_\varepsilon\ge\bar{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], i.e. $\mathrm{RS}=O(\mathrm{R})=O(3^d)$, not $\mathrm{RS}\ge\mathrm{R}$. The matching floor is direct: sabotage the all-zero input at one coordinate $i$. Both completions are legal ($\mathrm{NE}^d(0^n)=0$ while every weight-one input gives $1$), and every query to $j\ne i$ returns $0$, so nothing about $i$ leaks until it is queried; against the uniform distribution on the $3^d$ choices of $i$ a deterministic solver needs $(3^d+1)/2$ queries in expectation, and Yao gives $\mathrm{RS}=\Omega(3^d)$. BenDavidKothari18 |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(3^d\) | Squeeze: $\mathrm{R}\le\mathrm{R}^1\le\mathrm{D}$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(3^d)\) | Squeeze: $\bar{\mathrm{R}}\le\mathrm{R}=3^d$ and $\bar{\mathrm{R}}=\Omega(\mathrm{fbs})=\Omega(3^d)$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(3^d)\) | Maximised over input distributions: Yao's minimax gives $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(\Theta(3^d)\) putative | Certifying $\mathrm{NE}=1$ at the top means exhibiting two children with different values, so $\mathrm{C}_1(\mathrm{NE}^d)=\mathrm{C}_1(\mathrm{NE}^{d-1})+\mathrm{C}_0(\mathrm{NE}^{d-1})=\mathrm{C}_1(\mathrm{NE}^{d-1})+3^{d-1}$, and hence $\mathrm{C}_1(\mathrm{NE}^d)=(3^d+1)/2$. Even the $1$-side of certificate complexity is within a factor $2$ of the input length. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(3^{d/2})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. This is $\Theta(n^{1/2})$, well below $\mathrm{Q}=\Theta(n^{0.6845})$. |
| \(\lambda(f)\) Spectral sensitivity | \(3^{d/2}\) putative | The sensitivity graph of the $3$-bit gadget is two disjoint stars $K_{1,3}$ (the only $0$-inputs are $000$ and $111$), so $\lambda(\mathrm{NE})=\sqrt3$; spectral sensitivity is multiplicative under composition [ABKRT21], giving $\lambda(\mathrm{NE}^d)=3^{d/2}$. This meets the general floor $\lambda\ge\sqrt{\mathrm{s}}$ with equality, and sits below $\deg=2^d$ as $\lambda\le\deg$ requires. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(2.1213^d)\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Ambainis' lower bound for this family is in fact an adversary bound, so this line is where the recorded $\mathrm{Q}$ comes from. Reichardt11 |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(2.1213^d)\) | Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. LMRSS11 |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(2.1213^d)\) | Squeezed between $\mathrm{Adv}^{\pm}$ and $O(\mathrm{Q})$, which coincide. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(O(2^d)\) | Squeeze: $\widetilde{\deg}\le\deg=2^d$, with the floor $\widetilde{\deg}=\Omega(\sqrt{\mathrm{bs}})=\Omega(3^{d/2})$. Since $\widetilde{\deg}(\mathrm{NE})=\deg(\mathrm{NE})=2$ -- a symmetric $3$-bit function that is $0$ exactly at Hamming weights $0$ and $3$ admits no degree-$1$ approximation -- the true value is presumably $\Theta(2^d)$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(O(2.593^d)\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$; the floor is $\Omega(2.1213^d)$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(O(2.593^d)\) | The main theorem: $\mathrm{Q}_E(\mathrm{NE}^d) = O(2.593\ldots^d) = O(\mathrm{D}^{0.8675\ldots})$. The best known lower bound is only $\mathrm{Q}_E\ge\mathrm{Q}=\Omega(2.1213^d)$, so the exponent is not pinned; the value is recorded as $O(\cdot)$ for that reason. Ambainis13 |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(3^{d-1}\) putative | Exact. At a $1$-input of $\mathrm{NE}$ exactly one of the three coordinates is sensitive -- the odd one out, e.g. only $y_1$ at $y=011$ -- so $\mathrm{s}_1(\mathrm{NE}^d)=\max\{\mathrm{s}_0,\mathrm{s}_1\}(\mathrm{NE}^{d-1})=\mathrm{s}_0(\mathrm{NE}^{d-1})=3^{d-1}$, attained by putting the all-zero input into one child and $1$-inputs into the other two. So the fully sensitive input is essentially unique to the $0$-side: $\mathrm{s}_1$ is a factor $3$ below $\mathrm{s}_0=3^d$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(\Theta(3^d)\) putative | Lower: at the $1$-input above (child $1$ all-zero, children $2,3$ equal to $1$) each single bit of child $1$ is a sensitive block, giving $\mathrm{bs}_1\ge 3^{d-1}$. Upper: $\mathrm{bs}_1\le\mathrm{C}^1=(3^d+1)/2$. Unlike sensitivity, block sensitivity is maximal on both sides. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\Theta(2.3028^d)\) putative | Exact recursion. Let $a_d=\min_{x\in f^{-1}(0)}\mathrm{C}_x$ and $b_d=\min_{x\in f^{-1}(1)}\mathrm{C}_x$. A $0$-certificate must pin all three children (they must be shown equal): $a_d=3\min\{a_{d-1},b_{d-1}\}$. A $1$-certificate need only exhibit two children with different values: $b_d=a_{d-1}+b_{d-1}$. With $a_0=b_0=1$ one gets $b_d<a_d$ for all $d\ge1$, hence $a_d=3b_{d-1}$ and $b_d=b_{d-1}+3b_{d-2}$, i.e. $1,2,5,11,26,59,137,\dots$, whose growth rate is the root $(1+\sqrt{13})/2=2.3027\ldots$ So $\mathrm{C}_{\min}=\Theta(2.3028^d)=\Theta(n^{0.7587})$, strictly between $\lambda=n^{1/2}$ and $\mathrm{C}=n$. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\Omega(2.3028^d)\) | A Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=\Omega(2.3028^d)$; the ceiling is $\mathrm{rank}\le\mathrm{D}=3^d$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\Theta(3^d)\) | Squeeze: an unambiguous certificate family is in particular a certificate family, so $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=(3^d+1)/2$; and $\mathrm{UC}_{\min}\le\mathrm{UC}=3^d$. Both sides of this function are expensive to certify even ambiguously, so the [BHT17] route to a low-sensitivity function gets no traction here. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(3^d\) | For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=3^d$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)). |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(3^d\) | For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=3^d$. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(O(2.1213^d)\) | Squeeze: $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\Theta(2.1213^d)$. The floor is $\mathrm{Adv}\ge\sqrt{\mathrm{bs}}=3^{d/2}$ (equally $\mathrm{Adv}\ge\lambda$), so the positive adversary is pinned between $1.7320^d$ and $2.1213^d$ here. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(O(2^d)\) | Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}\le\deg=2^d$. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(O(2^d)\) | Squeeze: $\mathrm{sdeg}\le\widetilde{\deg}_+\le\deg=2^d$. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(O(2^d)\) | Squeeze: $\mathrm{rdeg}\le\deg=2^d$ (take the denominator $q\equiv 1$). |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(\Omega((5/3)^d)\) putative | Exact recursion. Coordinate $i$ of the top $\mathrm{NE}$ is sensitive at $y$ iff the other two children agree, an event independent of child $i$; hence $\mathrm{I}(\mathrm{NE}^d)=3\big(p_{d-1}^2+(1-p_{d-1})^2\big)\,\mathrm{I}(\mathrm{NE}^{d-1})$ with $p_d=\Pr[\mathrm{NE}^d=1]=3p_{d-1}(1-p_{d-1})$ and $\mathrm{I}(\mathrm{NE}^0)=1$. Since $p_d\to 2/3$, the factor tends to $3(4/9+1/9)=5/3$; the convergence is only neutral ($g'(2/3)=-1$), so the product picks up a $d^{o(1)}$ correction and only the lower bound $\mathrm{I}=\Omega((5/3)^d)$ is recorded (numerically the ratio $\mathrm{I}_d/(5/3)^d$ stays in $[0.9,1.2]$ out to $d=200$). Note $(5/3)^d=n^{0.4650}$, well below $\mathrm{s}=n$: the function is maximally sensitive at one input but only polynomially sensitive on average. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(\Omega((5/3)^d)\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}$. |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(\Omega((5/9)^d)\) | $\mathrm{NE}^d$ is transitive -- the automorphism group permuting the three children at every node acts transitively on the $3^d$ leaves -- so every coordinate has the same influence and $\mathrm{MaxInf}=\mathrm{I}/3^d=\Omega((5/9)^d)$. Individual influences are exponentially small even though $\mathrm{D}$ is maximal. |
| \(\mathrm{Var}(f)\) Variance | \(\Theta(1)\) | Exactly $8/9-o(1)$: $\Pr[\mathrm{NE}^d = 1] \to 2/3$, so $\mathrm{Var} = 4p(1-p) \to 8/9$; equivalently $1-\hat f(\emptyset)^2$ with the $1/9$ of the \(\mathrm{Stab}_{\rho}(f)\) entry. |
| \(\mathrm{osss}(f)\) OSSS number | \(O((9/5)^d) = O(N^{0.5350})\) putative | $\mathrm{Var} = \Theta(1)$ over $\mathrm{MaxInf} = \Omega((5/9)^d)$. Only an upper bound, because the recorded influence is only a lower bound; the matching direction would need the constant in the influence recursion. |
| \(\chi(f)\) Conflict complexity | \(\Theta(3^d)\) | Squeeze: $\chi=\Omega(\mathrm{bs})=\Omega(3^d)$ [Li18], and $\chi\le\bar\chi=O(\mathrm{LR})=O(\mathrm{R}^{*})\le O(\mathrm{R})=O(3^d)$. All four inner measures of randomized composition collapse to the arity here. Li18 |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(3^d)\) | Squeeze: $\bar\chi=\Omega(\mathrm{RS})=\Omega(3^d)$ [GLSS19] and $\bar\chi=O(\mathrm{LR})\le O(\mathrm{R})=O(3^d)$. GLSS19 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(3^d)\) | Squeeze: $\bar\chi=O(\mathrm{LR})$ and $\mathrm{LR}=O(\mathrm{R}^{*})\le\mathrm{R}$ [BBGM22]; both ends are $3^d$. This is the $\mathrm{LR}=\Theta(\mathrm{R})$ end of the range, as the recorded $\mathrm{RS}=\Theta(\mathrm{R})$ forces. BBGM22 |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(3^d)\) | Squeeze: $\mathrm{LR}=O(\mathrm{R}^{*})$ and $\mathrm{R}^{*}\le\mathrm{R}$ [BBGM22], both $\Theta(3^d)$. Iterating buys nothing, which is no surprise: $\mathrm{NE}^d$ is already an iterate, and $\mathrm{R}$ is exactly the arity at every depth. BBGM22 |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\widetilde\Theta(3^d)\) | Floor $\mathrm{N}_p=\Omega(\mathrm{R})=\Omega(3^d)$ (a clean algorithm simulates the noisy one by flipping each answer itself with probability $p$), ceiling $\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})=O(d\,3^d)$ [FRPU94]. Whether the $\log$ is paid is open here: the general floor $\mathrm{N}_p=\Omega(\mathrm{I}\log\mathrm{I})$ only gives $\Omega(d\,(5/3)^d)$, because the total influence of $\mathrm{NE}^d$ is exponentially below its arity -- unlike $\oplus_n$, which is why that function is known to need $\Theta(n\log n)$. FRPU94 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\widetilde\Theta(2.1213^d)\) | Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}$ and $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], with $\mathrm{Q}=\Theta(2.1213^d)$. BNRdW05 |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\Omega(2.3028^d)}\) | A decision tree with $L$ leaves has rank at most $\log_2 L$, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}\ge 2^{\mathrm{C}_{\min}}=2^{\Omega(2.3028^d)}$, against the ceiling $2^{\mathrm{D}}=2^{3^d}$. Doubly exponential in the asymptotic variable, hence recorded in a form the growth parser does not read. |
| \(\deg_2(f)\) Mod-2 degree | \(2^d\) putative | Exact. Over $\mathbb{F}_2$, $\mathrm{NE}=x_1+x_2+x_3+x_1x_2+x_1x_3+x_2x_3$, of degree $2$. Composing on disjoint blocks, the top-degree part of $\mathrm{NE}^d$ is $T_1T_2+T_1T_3+T_2T_3$ in the children's top parts $T_i$; the three products live on different pairs of blocks, so no cancellation is possible and the degree doubles at every level: $\deg_2(\mathrm{NE}^d)=2^d=\deg(\mathrm{NE}^d)$ (checked exhaustively for $d\le2$). Unlike $\oplus_n$, whose $\mathbb{F}_2$-degree collapses to $1$, this function is exactly as hard mod $2$ as over the reals. |
| \(\deg_p(f)\) Mod-p degree | \(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$. |
| \(\dim_{\mathbb{F}_2}(f)\) Fourier dimension | \(\Theta(3^d)\) putative | Exactly $2\cdot3^{d-1}$. In the $\pm1$ encoding $\mathrm{NE}=\tfrac12(-1+y_1y_2+y_1y_3+y_2y_3)$, so the Fourier support of $\mathrm{NE}^d$ consists of the sets $S_i\triangle S_j$ ($i<j$) with $S_i$ in the support of child $i$; since $\emptyset$ is in each child's support for $d\ge2$, taking $\mathbb{F}_2$-sums of two such sets recovers every $S_i$, so the span is the direct sum of the children's spans and $\dim_d=3\dim_{d-1}$ with $\dim_1=2$. Verified exhaustively for $d\le2$ ($2$ and $6$). So $\mathrm{NE}^d$ depends on $\tfrac23 n$ independent parities -- no parity structure to exploit. |
| \(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity | \(\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)$. |
| \(\mathrm{NS}_{\delta}(f)\) Noise sensitivity | \(\Theta(1)\) putative | For every constant $\delta\in(0,1/2)$. Push a $\delta$-correlated pair through the recursion: the joint law of $(\mathrm{NE}^d(x),\mathrm{NE}^d(y))$ is a $3$-fold product-then-gadget map on the four-state joint distribution, with marginal $p_d=\Pr[\mathrm{NE}^d=1]=3p_{d-1}(1-p_{d-1})\to2/3$. Iterating it numerically, the orbit is independent of $\delta$ (tested at $\delta$ corresponding to $\rho\in\{0.01,0.5,0.99\}$) from about $d=10$ on, and $\mathrm{NS}_\delta$ climbs to $4/9$ from below: $0.468$ at $d=30$, $0.452$ at $d=400$. So a constant flip rate destroys all correlation except what the bias forces. |
| \(\mathrm{Stab}_{\rho}(f)\) Noise stability | \(\Theta(1)\) putative | Same recursion as \(\mathrm{NS}_{\delta}(f)\): for every constant $\rho\in(0,1)$, $\mathrm{Stab}_\rho\to 1/9$, and numerically $\mathrm{Stab}_\rho$ agrees with $\hat f(\emptyset)^2=(1-2p_d)^2$ to six decimals by $d=30$ for $\rho$ anywhere in $[0.01,0.99]$. That is, $\mathrm{Stab}_\rho-\hat f(\emptyset)^2\to0$: all Fourier weight above level $0$ is noise-sensitive in the Benjamini-Kalai-Schramm sense, consistent with $\mathrm{MaxInf}=(5/9)^{d+o(d)}\to0$. $\mathrm{Stab}$ itself stays $\Theta(1)$ only because the function is biased. Note the contrast with $\mathrm{RS}=\mathrm{R}=3^d$: query complexity maximal, stability constant, exactly the incomparability that \(\mathrm{MAJ}_n\) witnesses. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(O(2^d)\) | Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=2^d$ (the certificate bound is the weaker one here, $(3^d+1)/2$). Already at $d=1$ the real form $x_1+x_2+x_3-(x_1x_2+x_1x_3+x_2x_3)$ is nonzero exactly on the $1$-inputs, so $\mathrm{ndeg}(\mathrm{NE})=2$. No floor is recorded: nondeterministic degree has no $\sqrt{\mathrm{bs}}$-type lower bound. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(O(2^d)\) | Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil\le 2^{d-1}$ (de Wolf), and $\mathrm{ndeg}\le\deg=2^d$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O(2^d)\) | Squeeze: $\mathrm{rdeg}_{1/3}\le\mathrm{rdeg}_0\le\deg=2^d$; approximation only helps. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(2^d)\) | Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] and $\mathrm{rdeg}_{1/3}\le\deg=2^d$. Not enough to decide whether post-selection beats $\mathrm{Q}=\Theta(2.1213^d)$ on this function, which would need a rational approximation genuinely below the real degree. MahadevdeWolf15 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\Omega(3^{d/2}),\ O(3^d)\) | Floor: dropping non-negativity gives $\mathrm{cjdeg}\ge\widetilde{\deg}=\Omega(\sqrt{\mathrm{bs}})=\Omega(3^{d/2})$. Ceiling: a depth-$\mathrm{D}$ decision tree is already an exact conical junta -- one width-$\le\mathrm{D}$ conjunction per accepting path, all coefficients $1$ -- so $\mathrm{cjdeg}\le\mathrm{D}=3^d$. |
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. 79 in total, strongest first.
-
\(\overline{\mathrm{prt}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Var}(f_n) = O(1)\)from \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(3^d)\) against \(\mathrm{Var}(f) = \Theta(1)\)
-
\(\mathrm{UC}_{\min}(f_n) = \Omega\big(\deg(f_n)^{1.585}\big)\)from \(\mathrm{UC}_{\min}(f) = \Theta(3^d)\) against \(\deg(f) = 2^d\)
-
\(\mathrm{s}(f_n) = \Omega\big(\mathrm{Q}_{\mathrm{E}}(f_n)^{1.153}\big)\)from \(\mathrm{s}(f) = 3^d\) against \(\mathrm{Q}_{\mathrm{E}}(f) = O(2.593^d)\)
-
\(\mathrm{s}^0(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{1.153}\big)\)from \(\mathrm{s}^0(f) = 3^d\) against \(\mathrm{Q}_{0}(f) = O(2.593^d)\)
-
\(\mathrm{UC}_{\min}(f_n) = \Omega\big(\deg_p(f_n)^{1.585}\big)\)from \(\mathrm{UC}_{\min}(f) = \Theta(3^d)\) against \(\deg_p(f) = 2^d\)
-
\(\mathrm{s}^0(f_n) = \Omega\big(\mathrm{Q}_{\mathrm{E}}(f_n)^{1.153}\big)\)from \(\mathrm{s}^0(f) = 3^d\) against \(\mathrm{Q}_{\mathrm{E}}(f) = O(2.593^d)\)
-
\(\mathrm{s}^1(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{1.153}\big)\)from \(\mathrm{s}^1(f) = 3^{d-1}\) against \(\mathrm{Q}_{0}(f) = O(2.593^d)\)
-
\(\mathrm{s}(f_n) = \Omega\big(\overline{\mathrm{prt}}_{\varepsilon}(f_n)\big)\)from \(\mathrm{s}(f) = 3^d\) against \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(3^d)\)
-
\(\mathrm{s}^1(f_n) = \Omega\big(\mathrm{Q}_{\mathrm{E}}(f_n)^{1.153}\big)\)from \(\mathrm{s}^1(f) = 3^{d-1}\) against \(\mathrm{Q}_{\mathrm{E}}(f) = O(2.593^d)\)
-
\(\mathrm{C}^1(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{1.153}\big)\)from \(\mathrm{C}^1(f) = \Theta(3^d)\) against \(\mathrm{Q}_{0}(f) = O(2.593^d)\)
-
\(\mathrm{s}^0(f_n) = \Omega\big(\overline{\mathrm{prt}}_{\varepsilon}(f_n)\big)\)from \(\mathrm{s}^0(f) = 3^d\) against \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(3^d)\)
-
\(\mathrm{bs}(f_n) = \Omega\big(\mathrm{Q}_{\mathrm{E}}(f_n)^{1.153}\big)\)from \(\mathrm{bs}(f) = 3^d\) against \(\mathrm{Q}_{\mathrm{E}}(f) = O(2.593^d)\)
-
\(\mathrm{bs}^0(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{1.153}\big)\)from \(\mathrm{bs}^0(f) = 3^d\) against \(\mathrm{Q}_{0}(f) = O(2.593^d)\)
-
\(\mathrm{fbs}(f_n) = \Omega\big(\overline{\mathrm{prt}}_{\varepsilon}(f_n)\big)\)from \(\mathrm{fbs}(f) = 3^d\) against \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(3^d)\)
… and 65 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{D} = \Omega(\mathrm{Q}_E^{1.15})$; the source of every "$1.15$" in the $\mathrm{Q}_E$ column. Upper bound $\mathrm{D}=O(\mathrm{Q}_E^3)$.
-
$\mathrm{C} = \Omega(\mathrm{Q}_E^{1.15})$.
-
$\mathrm{RC} = \Omega(\mathrm{Q}_E^{1.15})$.
-
$\mathrm{bs} = \Omega(\mathrm{Q}_E^{1.15})$.
-
$\mathrm{s} = \Omega(\mathrm{Q}_E^{1.15})$.
Cited as a witness by
-
\(\mathrm{D}(f_n) = \Omega(\mathrm{Q}_E(f_n)^{1.15})\)
Notes
Every combinatorial measure of $\mathrm{NE}^d$ is pinned to the input length by the all-zero input, which is sensitive in every coordinate. That makes this a rare entry where the whole left half of the table is exact: $\mathrm{s} = \mathrm{bs} = \mathrm{fbs} = \mathrm{RC} = \mathrm{C} = \mathrm{UC} = \mathrm{SP} = \mathrm{D} = \mathrm{R} = 3^d$, with only $\deg$, $\mathrm{Q}$ and $\mathrm{Q}_E$ dropping below it. Every "$1.15$" in the $\mathrm{Q}_E$ column is $1/0.8675\ldots$ read off against one of these.
Whether $2.593\ldots$ is the truth is open; [Ambainis13] asks both whether the algorithm can be improved and whether a better $\mathrm{Q}_E$ lower bound than $\mathrm{Q}$ exists. The largest possible gap is bounded by $\mathrm{D}=O(\mathrm{Q}_E^3)$ [Midrijanis04].