AND composed with NOT-EXACT-HALF
The witness for the whole rdeg column: $\mathrm{rdeg}=\Theta(n)$ while $\mathrm{s},\deg,\mathrm{D}=\Theta(n^2)$.
total
composed
arity: $N=n^2$ bits— also: \wedge\circ\overline{\mathrm{EH}}
Description
AND of $n$ copies of $\overline{\mathrm{EH}}_n$ (the negation of exact-half), on $N = n^2$ bits.
Formal definition
$$f(x^1,\dots,x^n) = \bigwedge_{j=1}^{n} \overline{\mathrm{EH}}_n(x^j) = \bigwedge_{j=1}^{n} \mathbb{1}\Big[\textstyle\sum_i x^j_i \ne \tfrac n2\Big].$$
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{rdeg}(f)\) Rational degree | \(\Theta(n) = \Theta(\sqrt N)\) | $\mathrm{ndeg}(f) = n \cdot \mathrm{ndeg}(\overline{\mathrm{EH}}_n) = n$ and $\mathrm{ndeg}(\bar f) = \mathrm{ndeg}(\mathrm{EH}_n) \le n$. IJKKKSWW23 |
| \(\lambda(f)\) Spectral sensitivity | \(\Theta(n^{3/2})\) | $\lambda(\mathrm{AND}_n)\cdot\lambda(\overline{\mathrm{EH}}_n) = \sqrt n\cdot\Theta(n)$. IJKKKSWW23 |
| \(\mathrm{s}(f)\) Sensitivity | \(\Theta(n^2)\) | IJKKKSWW23 |
| \(\deg(f)\) Exact degree | \(\Theta(n^2)\) | IJKKKSWW23 |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\Theta(n^2)\) | |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) | Lower from $\mathrm{Q}=\Omega(\lambda)$ and the recorded $\lambda = \Theta(n^{3/2})$. Upper by perfect composition $\mathrm{Q}(f\circ g)=O(\mathrm{Q}(f)\mathrm{Q}(g))$ [LMRSS11, Reichardt11] with $\mathrm{Q}(\mathrm{AND}_n)=\Theta(\sqrt n)$ and the trivial $\mathrm{Q}(\overline{\mathrm{EH}}_n)\le n$; the gadget really does cost $\Theta(n)$, since a symmetric function has $\mathrm{Q}=\Theta(\sqrt{n(n-\Gamma)})$ [BBCMdW01] and $\Gamma(\overline{\mathrm{EH}}_n)=1$. LMRSS11 Reichardt11 BBCMdW01 |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(n = \sqrt N\) putative | A $0$-input is sensitive only when exactly one block is at weight $n/2$ and the rest are $1$; then every bit of that block is pivotal and nothing else is. So $\mathrm{s}^0 = \mathrm{s}^0(\overline{\mathrm{EH}}_n) = n$ against $\mathrm{s}^1 = \Theta(n^2)$: all of the sensitivity of \(\mathrm{AND}_n \circ \overline{\mathrm{EH}}_n\) lives on the $1$-side. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(n^2/2 + n\) putative | At a $1$-input every block has weight $\ne n/2$, and a bit is pivotal exactly when its block sits at weight $n/2\pm1$ and the bit moves it to $n/2$; a block at weight $n/2\pm1$ has $n/2+1$ such bits. Taking all $n$ blocks there gives $\mathrm{s}^1 = n(n/2+1)$, which is the recorded $\mathrm{s} = \Theta(n^2)$. Brute force confirms $\mathrm{s}^1(\overline{\mathrm{EH}}_n) = n/2+1$ for $n \le 10$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(n = \sqrt N\) putative | Every sensitive block of a $0$-input must repair every zero block, so it meets each of them and at most $n$ of them are disjoint; the $n$ singletons of a single zero block achieve it. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(n^2/2 + n\) putative | Equal to $\mathrm{s}^1$: a sensitive block must push some block from weight $n/2+t$ to $n/2$, hence contains at least $t$ of that block's ones, so a block at distance $t$ supports at most $(n/2+t)/t$ disjoint sensitive blocks -- maximised at $t=1$, giving $n/2+1$ per block and $n(n/2+1)$ in all. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(n = \sqrt N\) putative | To certify $f = 0$ it suffices to pin one block at weight exactly $n/2$, which costs all $n$ of its bits and no fewer. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(n^2/2 + n\) putative | To certify $f = 1$ every block must be certified $\ne n/2$, and the cheapest witness for one block exhibits $n/2+1$ equal bits. So $\mathrm{C}^1 = n(n/2+1) = \Theta(N)$, matching the recorded $\mathrm{C}$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(n = \sqrt N\) putative | The $0$-inputs are far cheaper to certify than the $1$-inputs: $\mathrm{C}_{\min} = \mathrm{C}^0 = n = \sqrt N$ against $\mathrm{C} = \Theta(N)$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(N = n^2\) | Every variable is relevant, and a non-adaptive algorithm must read every relevant variable. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{fbs} = \Theta(n^2)$ and $\mathrm{D}^{\mathrm{na}} = n^2$ here. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Omega(n^{3/2}),\ O(n^2)\) | Between $\mathrm{Q} = \Theta(n^{3/2})$ and $\mathrm{D} = \Theta(n^2)$. The $\deg/2 = \Theta(n^2)$ floor is a $\mathrm{Q}_{\mathrm{E}}$ bound; the $\mathrm{Q}_0$ floor is $\mathrm{rdeg}/2 = \Theta(n)$, weaker than $\mathrm{Q}$ here. So whether forbidding error costs the last $\sqrt n$ is open as far as the zoo knows. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(\Theta(n^2)\) | A monochromatic subcube partition writes $f$ as a signless sum of subcube indicators of codimension $\le \mathrm{SP}$, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg$ and $\mathrm{D}$ are both $\Theta(n^2)$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\Theta(n^2)\) | Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D} = \Theta(n^2)$; see \(\mathrm{SP}(f)\). |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\Theta(n^2)\) | Between $\mathrm{fbs} = \Theta(n^2)$ and $\mathrm{C} = \Theta(n^2)$. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\tilde\Theta(n^{3/2})\) | The gadget has $\widetilde{\deg}(\overline{\mathrm{EH}}_n) = \Theta(n)$ by Paturi's symmetric-function formula $\Theta(\sqrt{n(n-\Gamma)})$ with $\Gamma = 1$ [Paturi92]. Upper: robustification gives $\widetilde{\deg}(f\circ g) = O(\widetilde{\deg}(f)\widetilde{\deg}(g)) = O(\sqrt n\cdot n)$ [Sherstov12robust]. Lower: $\widetilde{\deg}(f\circ g) = \tilde\Omega(\sqrt{\mathrm{bs}(f)}\,\widetilde{\deg}(g)) = \tilde\Omega(\sqrt n\cdot n)$ [CKMPSS23]. So $\widetilde{\deg} = \tilde\Theta(\mathrm{Q})$, and $\deg = \Theta(\widetilde{\deg}^{4/3})$ here. CKMPSS23 Sherstov12robust Paturi92 |
| \(\deg_2(f)\) Mod-2 degree | \(\Theta(n^2) = \Theta(N)\) putative | Over $\mathbb{F}_2$ the composition is the product $\prod_j \overline{\mathrm{EH}}_n(x^j)$ of polynomials on disjoint blocks, so $\deg_2$ adds: $\deg_2(f) = n\deg_2(\overline{\mathrm{EH}}_n)$. For the gadget the coefficient of a degree-$k$ monomial is $\binom{k}{n/2} \bmod 2$, so $\deg_2(\overline{\mathrm{EH}}_n)$ is the largest $k \le n$ whose binary expansion contains that of $n/2$ (Lucas); this is between $n/2$ and $n-1$, since $\binom{n}{n/2}$ is always even. Brute force gives $3,3,7,7$ at $n = 4,6,8,10$. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\Theta(n^2) = \Theta(N)\) putative | Upper $\mathrm{rank} \le \mathrm{D} = \Theta(n^2)$. Lower: in the Prover--Delayer game the Delayer defers on the first $n/2$ queries inside each block, scoring a point each time -- no $n/2$ bits of a block can decide $\overline{\mathrm{EH}}_n$, whose $\mathrm{C}_{\min}$ is $n/2+1$ -- and then answers the rest of that block so that it evaluates to $1$. The top $\mathrm{AND}_n$ is then undetermined until all $n$ blocks have been visited, so the Delayer scores $n\cdot n/2 = N/2$. Note this is much stronger than the generic $\mathrm{C}_{\min} \le \mathrm{rank}$, which only gives $\sqrt N$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\Theta(N)}\) | Between $2^{\mathrm{rank}}$ and $2^{\mathrm{D}}$, both $2^{\Theta(n^2)}$ by the \(\mathrm{rank}(f)\) entry. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\Theta(n^2)\) 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$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = \Theta(n^2)$, so both sides are pinned -- against $\mathrm{C}_{\min} = n$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(n) = \Theta(\sqrt N)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(n^2)$ here. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(n^2)\) | 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)) = \Theta(n^2)$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Theta(n^2)\) putative | Pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(n^2)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(n^2)$ -- take a $1$-input with every block at weight $n/2+1$ and star out a uniformly random one of the $n(n/2+1)$ disjoint sensitive blocks; all remaining bits look as usual, so finding a $\ast$ is unstructured search. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) | Sandwiched: $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, with $\lambda = \Theta(n^{3/2})$ and $\mathrm{Q} = \Theta(n^{3/2})$ here. The certificate barrier $\sqrt{\mathrm{C}^0\mathrm{C}^1} = \sqrt{n\cdot(n^2/2+n)} = \Theta(n^{3/2})$ sits at exactly the same place, so the positive adversary is maximal for this function. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/2})$ here. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) | $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/2})$ here. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) | Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants at $\Theta(n^{3/2})$ here. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(n = \sqrt N\) | The $\mathrm{ndeg}(f) = n$ half of the recorded \(\mathrm{rdeg}(f)\) value: $\mathrm{ndeg}(\overline{\mathrm{EH}}_n) = 1$, witnessed by $p(x) = \sum_i x_i - n/2$, and nondeterministic degree multiplies over the disjoint blocks of an AND, $\mathrm{ndeg}(\mathrm{AND}_n\circ g) = n\,\mathrm{ndeg}(g)$. IJKKKSWW23 |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\Theta(n) = \Theta(\sqrt N)\) | De Wolf's exact characterisation $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ applied to the \(\mathrm{ndeg}(f)\) entry. Nondeterministic quantum queries cost $\sqrt N$ while bounded-error ones cost $N^{3/4}$ and $\mathrm{D} = N$. IJKKKSWW23 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\widetilde\Omega(n^{3/2}),\ O(n^2)\) | Sandwiched: $\widetilde{\deg}_{\varepsilon} \le \mathrm{cjdeg}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\widetilde{\deg} = \tilde\Theta(n^{3/2})$ and $\mathrm{R} = \Theta(n^2)$ here. |
| \(\dim_{\mathbb{F}_2}(f)\) Fourier dimension | \(n^2-n = N-\sqrt N\) putative | The gadget's Fourier support is exactly the even-size sets (see \(\mathrm{spar}(f)\)), which span the even-weight subspace of $\mathbb{F}_2^{n}$, of dimension $n-1$. Since the support of the composition is the product of the blocks' supports, its $\mathbb{F}_2$-span is the direct sum of the $n$ even-weight subspaces, of dimension $n(n-1)$. So $\mathrm{D}^{\oplus} \le N - \sqrt N$: parity queries save something here, but only a $\sqrt N$ additive term. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(2^{-\Theta(\sqrt n)} = 2^{-\Theta(N^{1/4})}\) 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)} = 2^{-\Theta(N^{1/4})}\) putative | The function is transitive (permute blocks, permute inside a block, since $\overline{\mathrm{EH}}_n$ is symmetric), so every coordinate has influence exactly $\mathrm{I}(f)/N = 2c(1-c)^{n-1}$ with $c = \binom{n}{n/2}2^{-n}$; dividing by the polynomial factor $N$ does not touch the $e^{-\Theta(\sqrt n)}$ of the \(\mathrm{I}(f)\) entry. |
| \(\mathrm{Var}(f)\) Variance | \(2^{-\Theta(\sqrt n)} = 2^{-\Theta(N^{1/4})}\) | From $\mathrm{Var} = 2\,\mathrm{NS}_{1/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. The ratio to $\mathrm{MaxInf}$ is not pinned at this precision, so \(\mathrm{osss}(f)\) and \(\mathrm{nsr}(f)\) are not recorded for this function. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(2^{-\Theta(\sqrt n)} = 2^{-\Theta(N^{1/4})}\) putative | Exactly $\mathrm{I}(f) = 2n^2c\,(1-c)^{n-1}$ with $c = \binom{n}{n/2}2^{-n} = \Theta(n^{-1/2}) = \Pr[\overline{\mathrm{EH}}_n = 0]$: a bit of block $j$ is pivotal iff the other $n-1$ bits of its block are balanced to within one, which has probability $2c$, and every other block must be $1$. Since $cn = \Theta(\sqrt n)$, the factor $(1-c)^{n-1} = e^{-\Theta(\sqrt n)}$ swamps the polynomial $2n^2c = \Theta(n^{3/2})$. (Verified against the full Fourier expansion at $n = 4$: $\mathrm{I} = 2.9296875$.) |
| \(\hat{L}_1(f)\) Spectral norm | \(2^{\Theta(N)}\) putative | The blocks are disjoint, so $\widehat{L}_1(f) = |1 - 2q^n| + 2\big[\widehat{L}_1^{01}(\overline{\mathrm{EH}}_n)^n - q^n\big]$ with $q = 1-c$. The gadget's $0/1$ spectral norm is $2^{n/2}$ up to polynomial factors: Cauchy--Schwarz against $\sum_S \hat g(S)^2 = c$ gives $\widehat{L}_1^{01} \le \sqrt{\binom{n}{n/2}} \le 2^{n/2}$, and level $n/2$ alone contributes $\binom{n}{n/2}2^{-n}\binom{n/2}{n/4} = \Theta(2^{n/2}/n)$ when $n/2$ is even, because the Krawtchouk value there is $\pm\binom{n/2}{n/4}$. Hence $\widehat{L}_1(f) = 2^{(1/2-o(1))N}$. Exact value $19.1474\ldots$ at $n = 4$. |
| \(\mathrm{spar}(f)\) Fourier sparsity | \(2^{N-\sqrt N}\) putative | Sparsity is multiplicative over disjoint blocks, and the gadget has exactly $2^{n-1}$ nonzero coefficients: $\hat g(S)$ is $2^{-n}$ times a Krawtchouk value $K_{n/2}(|S|)$, which vanishes for every odd $|S|$ (complementation fixes the middle slice) and is nonzero for every even $|S|$ (checked for $n \le 18$). So $\mathrm{spar}(f) = (2^{n-1})^n = 2^{N-\sqrt N}$, near-maximal. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{bs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(n^2)\) | $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(n^2)$ here. |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(n^2)\) | $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(n^2)$ here. |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(n^2)\) | 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(n^2)\) | 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{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{R}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\chi(f)\) Conflict complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(n^2)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Theta(n^3) = \Theta(N^{3/2})\) | Pinned, and above the arity: the private-coin certificate game is not bounded by $\mathrm{D}$. Lower: $\mathrm{Adv} \ge \lambda = \Theta(n^{3/2})$, so $\mathrm{CG} \ge \mathrm{Adv}^2 = \Omega(n^3)$. Upper: $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = n\cdot(n^2/2+n) = \Theta(n^3)$. The two meet, so \(\mathrm{AND}_n \circ \overline{\mathrm{EH}}_n\) is a clean example of $\mathrm{CG} = \Theta(\mathrm{D}^{3/2})$ -- which is exactly what the large $\lambda$ of this function was built to produce. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Theta(n^2)\) | Sandwiched: $\deg(f) \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(n^2)\)· | Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(\Theta(n^2)\) | $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14], and $\mathrm{bs} = \Theta(n^2)$. GoosPitassi14 |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(n^2)\) | Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3}) = \Theta(n^2)$. Yao77 |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Omega(n^2),\ O(n^2\log n)\) | $\mathrm{N}_p \ge \mathrm{R} = \Omega(n^2)$, and majority-amplifying each query of the optimal randomized tree costs $O(\log \mathrm{R})$ [FRPU94]. FRPU94 |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(n^2)\) | $\mathrm{noisyR} \le \mathrm{R}$ always, and here $\mathrm{R} = \Theta(n^2) = \Theta(N)$ is of the order of the arity, which forces $\mathrm{noisyR} = \Theta(\mathrm{R})$ by the recorded implication [CKMPSS23]. BenDavidBlais20composition CKMPSS23 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Omega(n^{3/2}),\ O(n^{3/2}\log n)\) | $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n^{3/2})$, and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. The generic $O(N) = O(n^2)$ bound of [BNRdW05] is weaker. BNRdW05 |
| \(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity | \(\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$. |
| \(\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 each factor $1-(1-2\delta)^{|S|}$ with $|S|\ge1$ lies in $[2\delta,1]$. Each of the $n$ blocks is $1$ with probability $1-c$, $c = \Theta(n^{-1/2})$, so $\Pr[f=1] = (1-c)^n = 2^{-\Theta(\sqrt n)}$ and $\mathrm{Var} = 4p(1-p) = 2^{-\Theta(\sqrt n)}$ -- the same collapse that gives 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: the $\mathrm{AND}$ is almost always $0$, hence almost perfectly noise stable. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(\widetilde O(n^{3/2})\) | $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = \tilde\Theta(n^{3/2})$. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(\widetilde O(n^{3/2})\) | From $\mathrm{sdeg} \le \widetilde{\deg} = \tilde\Theta(n^{3/2})$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O(n) = O(\sqrt N)\) | Approximate rational degree is at most the exact rational degree, and the recorded $\mathrm{rdeg} = \Theta(n)$ is already a full power below $\widetilde{\deg} = \tilde\Theta(n^{3/2})$ and two powers below $\deg = \Theta(n^2)$. This is exactly the point of the function: rational approximation is cheap here even though polynomial approximation is not. IJKKKSWW23 |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(n) = O(\sqrt N)\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15], and $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = \Theta(n)$. So post-selection gives a genuine polynomial speed-up over ordinary quantum queries on this function: $O(\sqrt N)$ against $\mathrm{Q} = \Theta(N^{3/4})$. MahadevdeWolf15 IJKKKSWW23 |
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. 30 in total, strongest first.
-
\(\mathrm{DTsize}(f_n) = 2^{\Omega(\mathrm{RC}(f_n))}\)from \(\mathrm{DTsize}(f) = 2^{\Theta(N)}\) against \(\mathrm{RC}(f) = \Theta(n^2)\)
-
\(\mathrm{CG}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{3}\big)\)from \(\mathrm{CG}(f) = \Theta(n^3) = \Theta(N^{3/2})\) against \(\mathrm{rdeg}(f) = \Theta(n) = \Theta(\sqrt N)\)
-
\(\mathrm{s}^1(f_n) = \Omega\big(\mathrm{NQ}(f_n)^{2}\big)\)from \(\mathrm{s}^1(f) = n^2/2 + n\) against \(\mathrm{NQ}(f) = \Theta(n) = \Theta(\sqrt N)\)
-
\(\mathrm{C}^1(f_n) = \Omega\big(\mathrm{ndeg}(f_n)^{2}\big)\)from \(\mathrm{C}^1(f) = n^2/2 + n\) against \(\mathrm{ndeg}(f) = n = \sqrt N\)
-
\(\hat{L}_1(f_n) = \Omega\big(\mathrm{spar}(f_n)\big)\)from \(\hat{L}_1(f) = 2^{\Theta(N)}\) against \(\mathrm{spar}(f) = 2^{N-\sqrt N}\)
-
\(\mathrm{s}^1(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{2}\big)\)from \(\mathrm{s}^1(f) = n^2/2 + n\) against \(\mathrm{rdeg}(f) = \Theta(n) = \Theta(\sqrt N)\)
-
\(\mathrm{C}^1(f_n) = \Omega\big(\mathrm{NQ}(f_n)^{2}\big)\)from \(\mathrm{C}^1(f) = n^2/2 + n\) against \(\mathrm{NQ}(f) = \Theta(n) = \Theta(\sqrt N)\)
-
\(\mathrm{bs}^1(f_n) = \Omega\big(\mathrm{ndeg}(f_n)^{2}\big)\)from \(\mathrm{bs}^1(f) = n^2/2 + n\) against \(\mathrm{ndeg}(f) = n = \sqrt N\)
-
\(\mathrm{s}^1(f_n) = \Omega\big(\mathrm{ndeg}(f_n)^{2}\big)\)from \(\mathrm{s}^1(f) = n^2/2 + n\) against \(\mathrm{ndeg}(f) = n = \sqrt N\)
-
\(\mathrm{bs}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{2}\big)\)from \(\mathrm{bs}(f) = \Theta(n^2)\) against \(\mathrm{rdeg}(f) = \Theta(n) = \Theta(\sqrt N)\)
-
\(\mathrm{bs}^1(f_n) = \Omega\big(\mathrm{NQ}(f_n)^{2}\big)\)from \(\mathrm{bs}^1(f) = n^2/2 + n\) against \(\mathrm{NQ}(f) = \Theta(n) = \Theta(\sqrt N)\)
-
\(\mathrm{fbs}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{2}\big)\)from \(\mathrm{fbs}(f) = \Theta(n^2)\) against \(\mathrm{rdeg}(f) = \Theta(n) = \Theta(\sqrt N)\)
-
\(\mathrm{C}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{2}\big)\)from \(\mathrm{C}(f) = \Theta(n^2)\) against \(\mathrm{rdeg}(f) = \Theta(n) = \Theta(\sqrt N)\)
-
\(\mathrm{C}^1(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{2}\big)\)from \(\mathrm{C}^1(f) = n^2/2 + n\) against \(\mathrm{rdeg}(f) = \Theta(n) = \Theta(\sqrt N)\)
… and 16 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{D} = \Theta(\mathrm{rdeg}^2)$.
-
$\deg = \Theta(\mathrm{rdeg}^2)$ -- the largest separation known, and the lower end of the surviving gap now that $\deg = \widetilde O(\mathrm{rdeg}^3)$ [KKWY26] has answered Fortnow's question.
-
$\mathrm{s} = \Theta(\mathrm{rdeg}^2)$.
-
$\lambda = \Theta(\mathrm{rdeg}^{3/2})$; in particular $\lambda \le \mathrm{rdeg}$ is false, killing the hope of lower-bounding rdeg by spectral sensitivity.
Cited as a witness by
-
\(\mathrm{D}(f_n) = \Omega(\mathrm{rdeg}(f_n)^2)\)
-
\(\deg(f_n) = \Omega(\mathrm{rdeg}(f_n)^2)\)
-
\(\mathrm{s}(f_n) = \Omega(\mathrm{rdeg}(f_n)^2)\)
-
\(\widetilde{\deg}(f_n) = \Omega(\mathrm{rdeg}(f_n)^{3/2})\)
-
\(\lambda(f_n) = \Theta(n^{3/2}) \text{ while } \mathrm{rdeg}(f_n)=\Theta(n)\)