Kushilevitz's function (iterated)
A 6-variable function with $\deg = 3$ and $\mathrm{s}=6$; iterating gives $\mathrm{s} = \deg^{1.63}$.
total
composed
arity: $N = 6^k$ bits— also: the 6-variable degree-3 function, Nisan-Wigderson example
Description
Kushilevitz exhibited a function $K:\{0,1\}^6\to\{0,1\}$ with $\deg(K)=3$ but $\mathrm{s}(K)=\mathrm{bs}(K)=6$. Since $\deg$ is multiplicative under composition and $\mathrm{bs}$ is (at least) multiplicative, iterating $K$ gives $\deg = N^{\log_6 3}=N^{0.6131}$ against $\mathrm{bs} = N$, i.e. $\mathrm{bs} = \deg^{\log 6/\log 3} = \deg^{1.6309\ldots}$.
Formal definition
Identify the six coordinates with the projective line $\mathbb{P}^1(\mathbb{F}_5)=\{0,1,2,3,4,\infty\}$ and let $\mathcal{F}$ be the orbit of $\{\infty,0,1\}$ under $\mathrm{PSL}(2,5)$, a family of ten $3$-sets containing exactly one of each complementary pair. Then $$K(x) = 1 \iff |x| \in \{1,2,6\}\ \text{ or }\ \big(|x| = 3 \text{ and } \mathrm{supp}(x) \in \mathcal{F}\big).$$ Equivalently, in the $\pm1$ encoding, $$(-1)^{K(x)} \;=\; \tfrac14\Big(\textstyle\sum_{T\in\mathcal F}\chi_T(x) \;-\; \sum_{i=1}^{6}\chi_i(x)\Big),$$ which exhibits $\deg(K)=3$, $\widehat{L}_1(K)=4$, $\mathrm{spar}(K)=16$ and $\mathbb{E}[K]=\tfrac12$ at a glance. Up to permuting coordinates, negating individual coordinates and negating the output, this is the only $f:\{0,1\}^6\to\{0,1\}$ with $\deg(f) = 3$ and a fully sensitive input, and its automorphism group is exactly $\mathrm{PSL}(2,5)\cong A_5$ (order $60$, transitive on the six coordinates). The iterated function is $K^{\circ k}$ on $N = 6^k$ bits.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\deg(f)\) Exact degree | \(3^k = N^{0.6131}\) | |
| \(\mathrm{s}(f)\) Sensitivity | \(N = 6^k\) | |
| \(\mathrm{bs}(f)\) Block sensitivity | \(N\) | |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(N\) | |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(N)\) | |
| \(\mathrm{C}(f)\) Certificate complexity | \(N\) | |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(N\) | |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(N\) | |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(N\) | Between $\mathrm{fbs}=N$ and $\mathrm{C}=N$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(N\) | |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(N\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(N)\) | Sandwiched: $\mathrm{RC}(f) \le \mathrm{CA}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(N)$ and $\mathrm{fbs}(f) = N$ here. |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(N)\) | Sandwiched: $\mathrm{RC}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(N)$ and $\mathrm{fbs}(f) = N$ here. |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(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(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{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\chi(f)\) Conflict complexity | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Omega(N),\ O(N^2)\) | Not pinned. The private-coin certificate game is not bounded by $\mathrm{D}$; the correct sandwich is $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1,\ O(\mathrm{EC}^2)\}$. Lower: $\lambda = \sqrt N$ and $\mathrm{Adv} \ge \lambda$, so $\mathrm{Adv}^2 \ge N$ (the $\mathrm{R}_0 = N$ route gives the same). Upper: $\mathrm{C}^0\mathrm{C}^1 = N^2$, and $\mathrm{EC} = N$ gives the same $O(N^2)$. So $\mathrm{CG}$ can be as large as the square of the arity here and only a range is provable. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with both ends $N$ here. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(N)\)· | Sandwiched: $\mathrm{bs}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $N$ 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{s}^0(f)\) 0-sensitivity | \(N\) putative | The base function has $K(0^6)=0$ with all six coordinates sensitive, so the all-zero input of $K^{\circ k}$ has every block at $0^6$, every block value $0$, and every one of the $N$ bits sensitive. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(N\) putative | Mirror of $\mathrm{s}^0$: $K(1^6)=1$ (weight $6$ is a $1$-input, all six weight-$5$ neighbours are $0$-inputs), so the all-one input of $K^{\circ k}$ is fully sensitive as well. Kushilevitz's function is fully sensitive on both sides, which is what makes the $\mathrm{s}$-vs-$\deg$ separation survive negation. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(N\) | Between $\mathrm{s}^0 = N$ and the trivial ceiling $N$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(N\) | Between $\mathrm{s}^1 = N$ and the trivial ceiling $N$. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(N\) | Between $\mathrm{bs}^0 = N$ and the trivial ceiling $N$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(N\) | Between $\mathrm{bs}^1 = N$ and the trivial ceiling $N$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(4^k = N^{0.7737}\) putative | Exhaustive search over the $64$ inputs of the base function gives $\mathrm{C}_{\min}(K)=4$, attained on both sides ($\min_{K(x)=0}\mathrm{C}_x = \min_{K(x)=1}\mathrm{C}_x = 4$). Minimum certificate complexity composes: a certificate of $f\circ g^n$ at $x$ restricts to a certificate of $f$ at $g(x)$ on the blocks it certifies, so $\mathrm{C}_x(f\circ g^n) = \min_{S}\sum_{j\in S}\mathrm{C}_{x^j}(g)$ over certificates $S$ of $f$, and since $K$ is $4$ on both sides the minimum is $4\cdot\mathrm{C}_{\min}$ of the previous level. So $\mathrm{C}_{\min} = 4^k$ against $\mathrm{C} = 6^k$ -- a genuine gap, unlike \(\mathrm{AND}_n \circ \mathrm{OR}_n\) where the two coincide. |
| \(\deg_2(f)\) Mod-2 degree | \(3^k = N^{0.6131}\) putative | Mod-$2$ degree is exactly multiplicative under composition: the degree-$d_f$ part of $f$ over $\mathbb{F}_2$ is a sum of monomials in disjoint blocks, each of which becomes a product of the blocks' degree-$d_g$ parts, and distinct top monomials of $f$ land on distinct monomials, so nothing cancels. The base has $\deg_2(K)=3=\deg(K)$ (checked on the truth table), so $\deg_2 = \deg = 3^k$ here: characteristic $2$ buys nothing, and the $\mathrm{s}$-vs-$\deg$ separation is simultaneously an $\mathrm{s}$-vs-$\deg_2$ separation. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(N\) | Squeezed between $\mathrm{C} = N$ and $\mathrm{D} = N$, since $\mathrm{C} \le \mathrm{UC} \le \mathrm{SP} \le \mathrm{D}$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(N\) | Squeezed between $\mathrm{UC} = N$ and $\mathrm{D} = N$. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\Theta(N)\) putative | Between $N/2$ and $N$. Upper: $\mathrm{rank}\le\mathrm{D}=N$. Lower, by a Prover--Delayer argument that composes: $\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 inside each block -- so few bits can never determine that block's value -- and only then commits to the value the block will take, answering afterwards so as to force it. The order in which blocks reach that commitment is an adversary play against $f$, and the game cannot end until the completed blocks alone determine $f$, so at least $\mathrm{D}(f)$ blocks reach commitment, each paying $\mathrm{C}_{\min}(g)-1$ points. Here $\mathrm{C}_{\min}(K) = 4$ and $\mathrm{D}(K^{\circ k-1}) = 6^{k-1}$, so $\mathrm{rank} \ge 3\cdot 6^{k-1} = N/2$. Kushilevitz's function therefore has full rank up to a factor $2$: none of its depth is caterpillar, in contrast with $\mathrm{C}_{\min} = N^{0.77}$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\Theta(N)}\) putative | A decision tree of rank $r$ contains a complete binary branching of depth $r$ and so has at least $2^{r}$ leaves; with $\mathrm{rank} \ge N/2$ that gives $\mathrm{DTsize} \ge 2^{N/2}$, and $2^{\mathrm{D}} = 2^{N}$ is the ceiling. (The weaker generic bound $2^{\mathrm{C}_{\min}}$ would only give $2^{N^{0.77}}$.) |
| \(\lambda(f)\) Spectral sensitivity | \(6^{k/2} = \sqrt N\) | The sensitivity graph of the base function is a $60$-vertex-transitive graph on the cube with spectral norm exactly $\sqrt6$, and $\lambda$ is exactly multiplicative under composition, so $\lambda(K^{\circ k}) = 6^{k/2}$. Note this saturates Huang's inequality $\deg \le \lambda^2$ at the base ($3 \le 6$) but not asymptotically: $\lambda^2 = N$ while $\deg = N^{0.61}$. ABKRT21 |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\Omega(N^{0.6131}),\ O(N)\) putative | Not pinned. Lower: 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. $\mathrm{UC}_{\min} \ge \deg = 3^k$. Upper: $\mathrm{UC}_{\min} \le \mathrm{UC} = N$. Unlike the read-once functions in this file, $\deg \ne \mathrm{D}$ here, so the squeeze leaves a genuine $N^{0.39}$ window. |
| \(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity | \(\Omega(N^{0.6131}),\ O(N)\) putative | Not pinned. Upper: $\mathrm{D}^{\oplus}\le\mathrm{D}=N$. Lower by granularity: every coefficient of $K^{\circ k}$ is a product of base coefficients, each exactly $\pm\tfrac14$, and the number of factors obeys $F_k = 1 + 3F_{k-1}$ (choose one of the ten triples at every level), so the extreme coefficient is $\pm 4^{-(3^k-1)/2} = \pm 2^{-(3^k-1)}$ and the granularity is exactly $3^k-1$. [ChistopolskayaPodolskii18] then give $\mathrm{D}^{\oplus} \ge 3^k = \deg$. Parity queries can therefore save at most the $N^{0.39}$ by which $\deg$ falls short of $\mathrm{D}$. ChistopolskayaPodolskii18 |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(\sqrt N)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = N$ here. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(N)\) | 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)$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Theta(N)\) putative | Pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(N)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(N)$ -- at the fully sensitive input, star out one uniformly random coordinate; every other bit agrees with that input, so finding the $\ast$ is unstructured search over all $N$ positions. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Omega(\sqrt N),\ O(N)\) | Not pinned, for the same reason as \(\mathrm{Q}_{\varepsilon}(f)\): $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$ with $\lambda = \sqrt N$, and the certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = N$ is no better than the trivial ceiling here. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Omega(\sqrt N),\ O(N)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim; pinning it is the open question about the base function's adversary bound. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Omega(\sqrt N),\ O(N)\) | $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Omega(\sqrt N),\ O(N)\) | Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants; the window is that of \(\mathrm{Q}_{\varepsilon}(f)\). |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\Omega(\sqrt N),\ O(N)\) | Sandwiched: $\widetilde{\deg}_{\varepsilon} \le \mathrm{cjdeg}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\widetilde{\deg} = \Omega(\sqrt N)$ and $\mathrm{R} = \Theta(N)$ here. |
| \(\dim_{\mathbb{F}_2}(f)\) Fourier dimension | \(N = 6^k\) putative | The Fourier support of the base contains all six singletons (the $-\tfrac14\sum_i\chi_i$ term of the formal expansion), and taking the outer set $A = \{j\}$ at every level embeds each lower-level support set into a block, so every singleton of $[N]$ is in $\mathrm{supp}\widehat{K^{\circ k}}$. Singletons span $\mathbb{F}_2^N$, so $\dim_{\mathbb{F}_2} = N$ even though $\mathrm{spar} = 2^{\Theta(N^{0.61})}$ is far from full. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \((9/4)^k = N^{0.4526}\) 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 | \((3/8)^k = N^{-0.5474}\) putative | The automorphism group of the base is $\mathrm{PSL}(2,5)$, transitive on the six coordinates, so $K^{\circ k}$ is transitive and every coordinate has influence $\mathrm{I}(f)/N = (9/4)^k/6^k$. Maximum influence therefore decays even though $\mathrm{s} = N$: the fully sensitive inputs form a vanishing fraction of the cube. |
| \(\mathrm{Var}(f)\) Variance | \(1\) | The $\pm1$ Fourier expansion of the gadget recorded in the \(\mathrm{I}(f)\) entry has no constant term, so the gadget and every iterate of it is balanced. |
| \(\mathrm{osss}(f)\) OSSS number | \((8/3)^k = N^{0.5474}\) putative | $\mathrm{Var} = 1$ over $\mathrm{MaxInf} = (3/8)^k$. The function is transitive, so this is $N/\mathrm{I}(f) = 6^k/(9/4)^k$. Far short of $\mathrm{D} = \mathrm{R}_0 = N$, and short even of $\mathrm{s} = N$. |
| \(\mathrm{nsr}(f)\) Noise robustness | \(\Theta((9/4)^k) = \Theta(N^{0.4526})\) putative | The stability recursion $\Psi_K(\rho) = (3\rho+5\rho^3)/8$ of the \(\mathrm{NS}_{\delta}(f)\) entry acts as $1-\varepsilon\mapsto 1-\tfrac94\varepsilon$ near $\rho = 1$, so $\delta^{*} = \Theta((4/9)^k)$. Equal to $\mathrm{I}(f)$, so $\mathrm{osss}\cdot\mathrm{nsr} = \Theta(N)$ as for every transitive function whose $\mathrm{NS}_\delta\le\delta\mathrm{I}$ bound is tight. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \((9/4)^k = N^{0.4526}\) putative | The base is balanced, so under a uniform input the block values of $K\circ g^6$ are uniform and independent and total influence is exactly multiplicative: $\mathrm{I}(f\circ g^n) = \mathrm{I}(f)\,\mathrm{I}(g)$. From the Fourier expansion above, $\mathrm{I}(K) = 1\cdot 6\cdot(\tfrac14)^2 + 3\cdot 10\cdot(\tfrac14)^2 = \tfrac94$. So influence is only $N^{0.45}$ while $\mathrm{s} = N$: sensitivity here is concentrated on a vanishing fraction of the cube. |
| \(\hat{L}_1(f)\) Spectral norm | \(2^{\Theta(3^k)}\) putative | Because $K$ is balanced, $\widehat{K}(\emptyset)=0$ and the Fourier coefficients of a composition factor exactly: $\widehat{f\circ g}(T) = \widehat f(A)\prod_{j\in A}\widehat g(T_j)$ where $A$ is the set of blocks $T$ touches. Hence $\widehat L_1(f\circ g^n) = \sum_A|\widehat f(A)|\,\widehat L_1(g)^{|A|}$ with no cancellation, i.e. $\widehat L_1(K^{\circ k}) = \tfrac32\widehat L_1(K^{\circ k-1}) + \tfrac52\widehat L_1(K^{\circ k-1})^3$ from $\widehat L_1(K)=4$. The cubic recursion gives $\log \widehat L_1 = \Theta(3^k) = \Theta(\deg)$, comfortably under the universal ceiling $2^{N/2}$. |
| \(\mathrm{spar}(f)\) Fourier sparsity | \(2^{\Theta(N^{0.6131})}\) putative | The same factorisation as for \(\hat{L}_1(f)\), counting terms instead of adding them: $\mathrm{spar}(f\circ g^n) = \sum_{A\in\mathrm{supp}\widehat f}\mathrm{spar}(g)^{|A|}$. With the ten triples and six singletons of $\widehat K$ this is $\mathrm{spar}(k) = 6\,\mathrm{spar}(k-1) + 10\,\mathrm{spar}(k-1)^3$ from $\mathrm{spar}(0)=1$: $16, 41056, 6.9\cdot10^{14},\dots$, so $\log_2 \mathrm{spar} = \Theta(3^k) = \Theta(N^{\log_6 3})$. Sparsity is therefore governed by the degree, not by $N$: $K^{\circ k}$ has only $2^{N^{0.62}}$ of the $2^N$ possible coefficients, matching $\widehat L_1$. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Omega(\sqrt N),\ O(N^{0.6131})\) | Not pinned. Upper: $\widetilde{\deg}\le\deg = 3^k$. Lower: $\widetilde{\deg} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(\sqrt N)$. An LP over the $64$ inputs shows the base already has $\widetilde{\deg}(K) = \deg(K) = 3$, but no inner composition theorem for approximate degree is strong enough to iterate that (see comp-adeg). |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Omega(\sqrt N),\ O(N)\) | Not pinned. $\mathrm{Q}$ composes perfectly, so $\mathrm{Q}(K^{\circ k}) = \Theta(\mathrm{Adv}^{\pm}(K)^k)$ and the whole question is the value of the base adversary bound, which lies between $\lambda(K) = \sqrt6$ and $\mathrm{D}(K)=6$. The two ends give exactly $\sqrt N$ and $N$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Omega(\sqrt N),\ O(N)\) | The $\deg/2 = 3^k/2$ floor belongs to $\mathrm{Q}_{\mathrm{E}}$ (the row below), not to $\mathrm{Q}_0$: the zero-error floor is $\mathrm{rdeg}/2$, and $\mathrm{rdeg}$ is only bounded above by $3^k$ here. What is left is $\mathrm{Q} = \Omega(\sqrt N)$ underneath and $\mathrm{D} = N$ above. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Omega(N^{0.6131}),\ O(N)\) | Between $\deg/2 = 3^k/2$ and $\mathrm{D} = N$. Unlike \(\mathrm{AND}_n \circ \mathrm{OR}_n\) and \(\bar{\wedge}\text{-tree}\), where $\deg = \mathrm{D}$ forces $\mathrm{Q}_E = \Theta(\mathrm{D})$, here the degree bound leaves a genuine $N^{0.39}$ window. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(N\) | $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14], and $\mathrm{bs} = N$: the function is fully block sensitive. GoosPitassi14 |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(N)\) | Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3}) = \Theta(N)$. Yao77 |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Omega(N),\ O(N\log N)\) | $\mathrm{N}_p \ge \mathrm{R} = \Omega(N)$, and majority-amplifying each of the $\mathrm{R}$ queries costs a $O(\log \mathrm{R})$ factor [FRPU94]. FRPU94 |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(N)\) | $\mathrm{noisyR} \le \mathrm{R}$ always, and the recorded implication $\mathrm{R}(f) = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ applies since $\mathrm{R} = \Theta(N)$. CKMPSS23 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Omega(\sqrt N),\ O(N)\) | Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt N)$. Upper: $N$ noisy quantum queries recover the whole input with high probability [BNRdW05], so $\mathrm{Q}^{\mathrm{rob}} = O(N)$ for any function; this beats $O(\mathrm{Q}\log \mathrm{Q})$ because $\mathrm{Q}$ itself is only known up to an $N^{0.11}$ window here. BNRdW05 |
| \(\mathrm{NS}_{\delta}(f)\) Noise sensitivity | \(\tfrac{1}{2} - \Theta\big((3/8)^{\,k}\big)\) putative | The gadget is balanced, so $\mathrm{Stab}_\rho(f\circ g^m) = \mathrm{Stab}_{\mathrm{Stab}_\rho(g)}(f)$ applies. In $\pm 1$ the Kushilevitz gadget is $\tfrac14(\sum_{T\in\mathcal{F}}\chi_T - \sum_i \chi_i)$ with $|\mathcal{F}| = 10$ triples and $6$ singletons (Parseval: $(10+6)/16 = 1$; this also reproduces the recorded $\mathrm{I} = (30+6)/16 = 9/4$ and $\mathrm{MaxInf} = (5+1)/16 = 3/8$). Hence $\Psi_K(\rho) = (3\rho+5\rho^3)/8 < \rho$ on $(0,1)$, with $\Psi_K'(0) = 3/8$, so $\mathrm{Stab} = \Theta((3/8)^k)$ and $\mathrm{NS}_\delta = \tfrac12 - \Theta((3/8)^k)$. ODonnell14 NisanWigderson95 |
| \(\mathrm{Stab}_{\rho}(f)\) Noise stability | \(\Theta\big((3/8)^{\,k}\big) = \Theta(N^{-0.5474})\) putative | Iterating $\Psi_K(\rho) = (3\rho+5\rho^3)/8$ from the \(\mathrm{NS}_{\delta}(f)\) entry $k$ times drives any constant $\rho$ to $0$ at rate $3/8$ per level, so $\mathrm{Stab}_\rho = \Theta((3/8)^k) = \Theta(N^{\log_6(3/8)}) = \Theta(N^{-0.5474})$. Strongly noise sensitive, as the fully block-sensitive $\mathrm{bs} = N$ suggests. ODonnell14 |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(\le 3^k = N^{0.6131}\) | $\mathrm{ndeg} \le \deg = 3^k$ (a polynomial computing $f$ exactly is in particular nonzero exactly on $f^{-1}(1)$). The other generic bound $\mathrm{ndeg} \le \mathrm{C}^1 = N$ is much weaker here, which is the whole point of this function: its degree is polynomially smaller than its certificate complexity. IJKKKSWW23 |
| \(\mathrm{rdeg}(f)\) Rational degree | \(\le 3^k = N^{0.6131}\) | $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \deg(f) = 3^k$, since $\deg(\bar f) = \deg(f)$. Again far below $\mathrm{C} = N$. IJKKKSWW23 |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(O(N^{0.6131})\) | $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil \le 3^k/2$ [deWolf03], from the \(\mathrm{ndeg}(f)\) entry. deWolf03 |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(O(N^{0.6131})\) | $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(N^{0.6131})$; the lower end of the recorded $\widetilde{\deg}$ window, $\Omega(\sqrt N)$, comes from $\mathrm{bs} = O(\widetilde{\deg}^2)$ and does not transfer to the one-sided version. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(O(N^{0.6131})\) | From $\mathrm{sdeg} \le \widetilde{\deg} \le \deg = 3^k$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O(N^{0.6131})\) | At most $\widetilde{\deg} = O(N^{0.6131})$, and also at most $\mathrm{rdeg} \le 3^k$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(N^{0.6131})\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15], bounded by the \(\mathrm{rdeg}_{\varepsilon}(f)\) entry. MahadevdeWolf15 |
| \(\deg_p(f)\) Mod-p degree | \(3^k = N^{0.6131}\) putative | For every prime $p$. In the $0/1$ multilinear expansion $K = \tfrac12 - \tfrac18(\sum_{T\in\mathcal{F}}\chi_T - \sum_i\chi_i)$ with $\chi_S = \prod_{i\in S}(1-2x_i)$, the degree-$3$ part of $\chi_T$ is $-8\prod_{i\in T}x_i$, so each of the ten monomials $\prod_{i\in T}x_i$ carries coefficient exactly $+1$ -- nonzero modulo every $p$. Under self-composition the top-degree part is $\sum_{T\in\mathcal{F}}\prod_{i\in T}(\text{top part of the } i\text{-th copy})$, a sum of distinct monomials over disjoint blocks, so no cancellation is possible and $\deg_p = 3^k$ for all $p$, matching the recorded $\deg_2$. |
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. 60 in total, strongest first.
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{NS}_{\delta}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(N)\) against \(\mathrm{NS}_{\delta}(f) = \tfrac{1}{2} - \Theta\big((3/8)^{\,k}\big)\)
-
\(\mathrm{s}(f_n) = \Omega\big(\deg(f_n)^{1.6309}\big)\)from \(\mathrm{s}(f) = N = 6^k\) against \(\deg(f) = 3^k = N^{0.6131}\)
-
\(\mathrm{s}^0(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{1.6309}\big)\)from \(\mathrm{s}^0(f) = N\) against \(\mathrm{rdeg}(f) = \le 3^k = N^{0.6131}\)
-
\(\mathrm{s}^1(f_n) = \Omega\big(\deg_p(f_n)^{1.6309}\big)\)from \(\mathrm{s}^1(f) = N\) against \(\deg_p(f) = 3^k = N^{0.6131}\)
-
\(\mathrm{C}_{\min}(f_n) = \Omega\big(\mathrm{NQ}(f_n)^{1.262}\big)\)from \(\mathrm{C}_{\min}(f) = 4^k = N^{0.7737}\) against \(\mathrm{NQ}(f) = O(N^{0.6131})\)
-
\(\mathrm{noisyR}(f_n) \to \infty \ \text{ while } \ \mathrm{NS}_{\delta}(f_n) = O(1)\)from \(\mathrm{noisyR}(f) = \Theta(N)\) against \(\mathrm{NS}_{\delta}(f) = \tfrac{1}{2} - \Theta\big((3/8)^{\,k}\big)\)
-
\(\mathrm{s}(f_n) = \Omega\big(\deg_p(f_n)^{1.6309}\big)\)from \(\mathrm{s}(f) = N = 6^k\) against \(\deg_p(f) = 3^k = N^{0.6131}\)
-
\(\mathrm{s}^0(f_n) = \Omega\big(\deg(f_n)^{1.6309}\big)\)from \(\mathrm{s}^0(f) = N\) against \(\deg(f) = 3^k = N^{0.6131}\)
-
\(\mathrm{bs}^0(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{1.6309}\big)\)from \(\mathrm{bs}^0(f) = N\) against \(\mathrm{rdeg}(f) = \le 3^k = N^{0.6131}\)
-
\(\mathrm{R}^{*}(f_n) \to \infty \ \text{ while } \ \mathrm{NS}_{\delta}(f_n) = O(1)\)from \(\mathrm{R}^{*}(f) = \Theta(N)\) against \(\mathrm{NS}_{\delta}(f) = \tfrac{1}{2} - \Theta\big((3/8)^{\,k}\big)\)
-
\(\mathrm{s}^0(f_n) = \Omega\big(\deg_p(f_n)^{1.6309}\big)\)from \(\mathrm{s}^0(f) = N\) against \(\deg_p(f) = 3^k = N^{0.6131}\)
-
\(\mathrm{s}^1(f_n) = \Omega\big(\deg(f_n)^{1.6309}\big)\)from \(\mathrm{s}^1(f) = N\) against \(\deg(f) = 3^k = N^{0.6131}\)
-
\(\mathrm{C}_{\min}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{1.2619}\big)\)from \(\mathrm{C}_{\min}(f) = 4^k = N^{0.7737}\) against \(\mathrm{rdeg}(f) = \le 3^k = N^{0.6131}\)
-
\(\deg_p(f_n) \to \infty \ \text{ while } \ \mathrm{NS}_{\delta}(f_n) = O(1)\)from \(\deg_p(f) = 3^k = N^{0.6131}\) against \(\mathrm{NS}_{\delta}(f) = \tfrac{1}{2} - \Theta\big((3/8)^{\,k}\big)\)
… and 46 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{bs} = \Omega(\deg^{1.63})$; the best known separation against the upper bound $\mathrm{bs}\le 2\deg^2$.
-
$\mathrm{s} = \Omega(\deg^{1.63})$ vs the upper bound $\mathrm{s}\le\deg^2$ (Huang).
-
$\mathrm{RC} = \Omega(\deg^{1.63})$.
Cited as a witness by
-
\(\mathrm{bs}(f_n) = \Omega\big(\deg(f_n)^{\log 6/\log 3}\big) = \Omega(\deg(f_n)^{1.6309})\)