Q The Query Complexity Zoo
\(f = f(|x|)\)

Symmetric functions (general)

Every measure in the polynomial/quantum column is pinned down exactly by Paturi's theorem.

total basic arity: $n$ bits

Description

$f$ is symmetric if $f(x)$ depends only on the Hamming weight $|x|$; write $f(x) = f_{|x|}$. Let $$\Gamma(f) \;=\; \min\{\,|2k-n+1| \;:\; f_k \ne f_{k+1}\,\}$$ measure how close to the middle layer the "jump" is.

Formal definition

$f:\{0,1\}^n\to\{0,1\}$ with $f(x)=f(\sigma x)$ for all permutations $\sigma$. Equivalently $f = g \circ (\sum_i x_i)$ for some $g : \{0,\dots,n\}\to\{0,1\}$.

Measure values

MeasureValueNotes
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) Paturi92
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) Approximate degree characterises $\mathrm{Q}$ exactly (up to constants) for symmetric functions. BBCMdW01 Paturi92
\(\deg(f)\) Exact degree \(n - O(n^{0.548})\) What is proved: von zur Gathen--Roche show $\deg(f) \ge n - O(n^{0.548})$ for every non-constant symmetric $f$, and $\deg(f)\le n$ is trivial, so $\deg(f) = n - O(n^{0.548})$. Their exponent comes from prime gaps: $\deg(f) = n - O(g(n))$ where $g$ bounds the gap below $n$, so any improvement on prime gaps improves this line automatically, and the Riemann Hypothesis would give $n - O(\sqrt n\log n)$. Conjecturally the truth is $\deg(f) \in \{n, n-1\}$ for every non-constant symmetric $f$ -- i.e. $\deg(f) = n - O(1)$; it has been checked exhaustively for small $n$, and it holds for every $f$ whose jump structure is a single threshold (see \(\mathrm{THR}^n_k\), where $\deg = n$ exactly). vzGathenRoche97
\(\mathrm{D}(f)\) Deterministic query complexity \(n \text{ (for all but trivial } f)\)
\(\mathrm{rdeg}(f)\) Rational degree \(\Omega(\deg(f))\) Asymptotically tight: symmetric functions cannot separate rdeg from deg. IJKKKSWW23
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) A non-degenerate symmetric function depends on every coordinate.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) $\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\!\big(\sqrt{n(n-\Gamma(f))}\big)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) $\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\!\big(\sqrt{n(n-\Gamma(f))}\big)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)$ here.
\(\mathrm{s}(f)\) Sensitivity \(\Theta(n)\) putative Pick any $k$ with $f_k \ne f_{k+1}$. At an input of weight $k$ all $n-k$ zeros are sensitive, and at an input of weight $k+1$ all $k+1$ ones are, so $\mathrm{s}(f) \ge \max\{k+1,\,n-k\} \ge \lceil (n+1)/2\rceil$. Every non-constant symmetric function therefore has sensitivity $\Theta(n)$ -- this, and not the degree, is the reason symmetric functions are uninteresting for the classical measures: everything from $\mathrm{s}$ up to $\mathrm{D}$ collapses to $\Theta(n)$ regardless of $\Gamma(f)$.
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{bs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(n)\) $\mathrm{FC}(f) = \mathrm{fbs}(f)$ exactly, by LP duality. Tal13
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, with both ends $\Theta(n)$ here. GJKKLSSV17
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) $\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$, and $\mathrm{fbs}(f) = \Theta(n)$ here. Aaronson08
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(n)$ here. ABIKPS17
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ for every $f$, and $\mathrm{CA}(f) = \Theta(n)$ here. CGLMSG23
\(\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. In particular $\mathrm{CG}^{*}$ is $\Theta(n)$ for every symmetric function, however small $\mathrm{Q}$ gets. 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{CG}(f)\) Certificate game complexity (private coin) \(\Omega(n),\ O(n^2)\) The [CGLMSG23] sandwich is $\max\{\mathrm{Adv}^2, \mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$, and for a generic non-constant symmetric $f$ only $\mathrm{R}_0 = \Theta(n)$ is available below while $\mathrm{C}^0\mathrm{C}^1 = O(n^2)$ caps it above. Which end is reached depends on the function: it is $\Theta(n)$ for \(\mathrm{OR}_n\) and $\Theta(n^2)$ for \(\oplus_n\) and \(\mathrm{MAJ}_n\), both of which are symmetric, so no single value can be recorded for the whole class. CGLMSG23
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f)/3 \le \mathrm{R}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. Randomization never helps on a symmetric function, in sharp contrast with $\mathrm{Q}$, which drops to $\Theta(\sqrt n)$ when the jump is at the edge.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) Sandwiched between $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Sandwiched between $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) Sandwiched between $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Sandwiched between $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help. CKMPSS23
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. So every symmetric function composes perfectly on the inside. BenDavidKothari18
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Sandwiched: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Sandwiched: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(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{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) Sandwiched: $\deg(f)/2 \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, and von zur Gathen-Roche makes $\deg(f) = n - O(n^{0.548})$, so both ends are $\Theta(n)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\) Between $\mathrm{rdeg}(f)/2$ and $\mathrm{D}(f)$, both $\Theta(n)$: one of the two sides $\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)$ counts at least half of the $n+1$ levels, since together they count them all. (The $\deg(f) \le 2\mathrm{Q}_0$ used for $\mathrm{Q}_{\mathrm{E}}$ is not available for $\mathrm{Q}_0$; for symmetric $f$ it happens not to matter.) Zero error costs the full $n$ for every symmetric function, however small $\Gamma(f)$ makes the bounded-error value.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. Aaronson08
\(\mathrm{sdeg}(f)\) Sign degree \(\#\{k \,:\, f_k \ne f_{k+1}\}\) putative Exactly the number of jumps of the slice pattern. Symmetrizing a sign-representing polynomial keeps it sign-representing, so $\mathrm{sdeg}(f)$ equals the least degree of a univariate $q$ on $\{0,\dots,n\}$ with $\mathrm{sign}\,q(j) = (-1)^{f_j}$; such a $q$ needs a root strictly between each pair of consecutive jumps, and $\prod_i(|x| - a_i)$ with one $a_i$ in each gap attains the bound. Recovers $\mathrm{sdeg}(\mathrm{THR}) = 1$ and $\mathrm{sdeg}(\mathrm{EH}) = 2$. Note this is a display-only value: it is not a function of $n$ and $\Gamma(f)$.
\(\lambda(f)\) Spectral sensitivity \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) putative The sensitivity graph is the union, over the jumps $k$ of the slice pattern, of the complete bipartite layer graphs between Hamming levels $k$ and $k+1$; that piece is biregular of degrees $n-k$ and $k+1$, so it has spectral norm $\sqrt{(k+1)(n-k)}$. Each vertex lies in at most two pieces, so $\lambda$ is within a factor $2$ of the largest piece, and the jump maximising $(k+1)(n-k)$ is the one closest to the middle, i.e. the one defining $\Gamma(f)$: $(k+1)(n-k) = \Theta(n(n-\Gamma(f)))$. So spectral sensitivity is $\Theta(\mathrm{Q}(f))$ for every symmetric function -- Huang's $\deg \le \lambda^2$ is tight exactly at the edge-jump end, $\Gamma = n-1$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) putative Squeezed: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)$ from the line above and $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$ the same quantity. The positive-weight adversary is therefore tight on the whole symmetric class; no symmetric function can witness the certificate barrier.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(n)\) Squeezed: $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f) - 1$ [BHT17] forces $\mathrm{UC}_{\min} = \Omega(n)$ since $\mathrm{fbs} = \Theta(n)$ here, and $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. So symmetric functions are useless for the $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ separation of [BHT17]. BHT17
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\Theta(\#\{j \,:\, f_j = 0\})\) putative Upper: $\prod_{j : f_j = 0}(|x|-j)$ is nonzero exactly on the $1$-inputs. Lower: if $p$ witnesses $\mathrm{ndeg}$ then $p^2$ is non-negative, vanishes exactly on the $0$-inputs, and its symmetrisation $j \mapsto \mathbb{E}_{|x|=j}[p(x)^2]$ is a univariate polynomial of degree at most $2\deg p$ that is strictly positive on the $1$-slices and zero on the $0$-slices, hence has at least $\#\{j : f_j = 0\}$ roots. So $\mathrm{ndeg}$ is pinned to within a factor $2$. Like the \(\mathrm{sdeg}(f)\) line this is a display-only value: it is a function of the slice pattern, not of $n$ and $\Gamma(f)$. Recovers $\mathrm{ndeg}(\mathrm{OR}) = 1$, $\mathrm{ndeg}(\mathrm{AND}) = n$ and $\mathrm{ndeg}(\mathrm{THR}^n_k) = k$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Theta(\#\{j \,:\, f_j = 0\})\) putative de Wolf's $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ applied to the \(\mathrm{ndeg}(f)\) line above. Nondeterministic quantum query complexity of a symmetric function is governed by the number of $0$-slices, not by where they sit -- in sharp contrast with $\mathrm{Q}$, which sees only the distance $\Gamma(f)$ of the nearest jump to the middle layer. deWolf00
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\) putative Take the product distribution with each bit $1$ independently with probability $k/n$, where $k$ is a jump. After $m$ queries the unseen part of the weight is a $\mathrm{Bin}(n-m,k/n)$ variable whose standard deviation is $\Omega(\sqrt{n-m})$, so the conditional probability of landing on either side of the jump stays bounded away from $0$ and $1$ until $n-m = O(1)$. Product distributions are already worst case for symmetric functions.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$ for every non-constant symmetric $f$, by the \(\mathrm{R}_{\varepsilon}(f)\) line; the \(\mathrm{D}^{\mathrm{prod}}(f)\) line exhibits a product distribution that attains it. Yao77
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(n)\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, and $\mathrm{bs}(f) = \Theta(n)$ for every non-constant symmetric $f$ by the \(\mathrm{bs}(f)\) line. GoosPitassi14
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$ by the \(\mathrm{R}_{\varepsilon}(f)\) line. CDM23
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(n)\)· putative Fix a jump $k$, so $f_k \ne f_{k+1}$. Restricting $k$ variables to $1$ leaves a function $g$ on $m = n-k$ variables with $g(0^m) \ne g(e_i)$ for every $i$; restricting $n-k-1$ variables to $0$ leaves a function on $k+1$ variables with the corresponding property at $1^{k+1}$. In either case the \(\mathrm{OR}_n\) / \(\mathrm{AND}_n\) argument applies verbatim -- a width-$d$ conjunction can separate $0^m$ from at most $d$ of the $e_i$ -- and a conical junta restricts to a conical junta of no larger width, so $\mathrm{cjdeg} = \Omega(\max\{k+1,\ n-k\}) = \Omega(n)$. Upper: $\mathrm{cjdeg}_{\varepsilon} \le \mathrm{D} = n$. So non-negativity destroys Paturi's $\widetilde{\deg} = \Theta(\sqrt{n(n-\Gamma(f))})$ saving for every symmetric $f$, however small $\Gamma$ is.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) Same as the recorded $\mathrm{Q}$, since $n - \Gamma(f) \ge 1$ for non-constant $f$. Theorem 4 of [BNRdW05]: for every symmetric $f$ there is a robust quantum algorithm using $O(\sqrt{n(n-\Gamma(f)+1)})$ queries -- robust counting suffices, since $f$ is constant on the middle band of weights of width $\Gamma(f)$. The matching lower bound is $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt{n(n-\Gamma(f))})$ by Paturi (the \(\mathrm{Q}_{\varepsilon}(f)\) line). So the whole symmetric family tolerates noisy inputs for free, in contrast with the classical $\log$ tax at \(\oplus_n\) and \(\mathrm{MAJ}_n\). BNRdW05
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(n),\ O(n\log n)\)· Lower: $\mathrm{N}_p \ge \mathrm{R} = \Theta(n)$. Upper: $O(\mathrm{R}\log\mathrm{R})$ by repeating each query. Recorded as a range because both ends occur inside the family and are not a function of $\Gamma$ alone: \(\mathrm{OR}_n\) sits at $\Theta(n)$ [FRPU94] while \(\oplus_n\), \(\mathrm{MAJ}_n\) and \(\mathrm{EH}_n\) all need $\Theta(n\log n)$. The general bound $\mathrm{N}_p = \Omega(\mathrm{I}\log\mathrm{I})$ [GLX26noisy] together with the \(\mathrm{I}(f)\) line decides many individual cases. FRPU94 GLX26noisy
\(\mathrm{I}(f)\) Total influence (L2 influence) \(n\,2^{1-n}\sum_{k \,:\, f_k \ne f_{k+1}}\binom{n-1}{k}\) putative Exactly. Coordinate $i$ is pivotal at $x$ precisely when the other $n-1$ bits have weight $k$ for some jump $f_k \ne f_{k+1}$, an event of probability $2^{1-n}\binom{n-1}{k}$; sum over jumps and over the $n$ coordinates. Checks: $\vee_n$ (single jump at $k=0$) gives $n2^{1-n}$; $\oplus_n$ (all $n$ jumps) gives $n$; $\mathrm{THR}^n_k$ gives $n\binom{n-1}{k-1}2^{1-n}$; \(\mathrm{EH}_n\) gives $\Theta(\sqrt n)$. Displayed as a formula in the slice pattern rather than in $n$ and $\Gamma$, since $\Gamma$ does not determine it.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(n\,2^{1-n}\sum_{k \,:\, f_k \ne f_{k+1}}\binom{n-1}{k}\) Boolean-valued, so the $L_1$ and $L_2$ total influences coincide: this is the $\mathrm{I}(f)$ recorded above.
\(\mathrm{MaxInf}(f)\) Maximum influence \(2^{1-n}\sum_{k \,:\, f_k \ne f_{k+1}}\binom{n-1}{k}\) putative The family is transitive, so every coordinate carries the same influence $\mathrm{I}(f)/n$; divide the \(\mathrm{I}(f)\) line by $n$.
\(\mathrm{Var}(f)\) Variance \(4p(1-p),\quad p = 2^{-n}\sum_{j\,:\,f_j = 1}\binom nj\) Determined by the level set alone, like every other quantity on this page.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\max\{\,\ell_j + n - r_j \;:\; f_j = 1\,\}\) putative Exactly. Write $[\ell_j, r_j]$ for the maximal interval of weights containing $j$ on which the slice pattern is constant. A certificate at an input of weight $j$ fixes $a$ ones and $b$ zeros, and the completions have every weight in $[a,\ n-b]$, so it is valid iff $a \ge \ell_j$ and $n-b \le r_j$; both are attainable, since $\ell_j \le j$ ones and $n - r_j \le n-j$ zeros are available. Hence $\mathrm{C}_x = \ell_j + n - r_j$, and $\mathrm{C}^1$ maximises over $1$-inputs. Checks: $\vee_n$ gives $1$, $\mathrm{THR}^n_k$ gives $k$, $\oplus_n$ gives $n$, \(\mathrm{EH}_n\) gives $n$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\max\{\,\ell_j + n - r_j \;:\; f_j = 0\,\}\) putative Same computation as the \(\mathrm{C}^1(f)\) line, maximised over $0$-inputs: with $[\ell_j, r_j]$ the maximal constancy interval of the slice pattern around $j$, a minimum certificate at weight $j$ costs $\ell_j$ ones plus $n - r_j$ zeros. Checks: $\vee_n$ gives $n$, $\mathrm{THR}^n_k$ gives $n-k+1$, \(\mathrm{EH}_n\) gives $n/2+1$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\min_j\,(\ell_j + n - r_j)\) putative The same per-input formula as the \(\mathrm{C}^1(f)\) line, minimised rather than maximised over all weights $j$. Equivalently $n$ minus the length of the longest constancy interval of the slice pattern, plus one. Checks: $\vee_n$ gives $1$, $\mathrm{THR}^n_k$ gives $\min\{k,\ n-k+1\}$, $\oplus_n$ gives $n$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(\max\{\,j\,[f_{j-1} \ne f_j] + (n-j)\,[f_j \ne f_{j+1}] \;:\; f_j = 1\,\}\) putative Exactly. At an input of weight $j$, flipping one of the $j$ ones moves the weight to $j-1$ and flipping one of the $n-j$ zeros moves it to $j+1$, so the sensitivity is that count (reading $f_{-1}, f_{n+1}$ as "no jump"). Maximise over $1$-inputs. Checks: $\vee_n$ gives $1$, $\wedge_n$ gives $n$, $\mathrm{THR}^n_k$ gives $k$, \(\mathrm{EH}_n\) gives $n$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\max\{\,j\,[f_{j-1} \ne f_j] + (n-j)\,[f_j \ne f_{j+1}] \;:\; f_j = 0\,\}\) putative The same per-input count as the \(\mathrm{s}^1(f)\) line, maximised over $0$-inputs. Checks: $\vee_n$ gives $n$, $\wedge_n$ gives $1$, $\mathrm{THR}^n_k$ gives $n-k+1$, \(\mathrm{EH}_n\) gives $n/2+1$. Together with \(\mathrm{s}^1(f)\) this recovers the recorded $\mathrm{s}(f) = \max\{\mathrm{s}^0, \mathrm{s}^1\} = \Theta(n)$.