Spectral sensitivity
Largest eigenvalue of the adjacency matrix of the sensitivity graph of f.
also written:
Koutsoupias' K(f), largest eigenvalue of the sensitivity graph
Definition
The sensitivity graph $G_f$ has vertex set $\{0,1\}^n$ and an edge $\{x,x^{\oplus i}\}$ whenever $f(x)\ne f(x^{\oplus i})$. Then $\lambda(f) = \|A_{G_f}\|$, the spectral norm of its adjacency matrix.
Introduced (under this name) by Aaronson-Ben-David-Kothari-Rao-Tal; it coincides with Koutsoupias' $K(f)$ and is a lower bound on essentially everything, while Huang's theorem in its strongest form reads $\deg(f)\le\lambda(f)^2$.
Basic facts
- $\sqrt{\mathrm{s}(f)} \le \lambda(f) \le \mathrm{s}(f)$ and $\lambda(f)\le\sqrt{\mathrm{s}^0(f)\mathrm{s}^1(f)}$.
- $\deg(f) \le \lambda(f)^2$ (Huang's theorem, spectral form) and $\lambda(f)\le\deg(f)$.
- $\lambda(f) = O(\widetilde{\deg}(f))$ [ABKRT21, Thms 17-18].
- $\lambda(f) \le \mathrm{Adv}(f) = O(\mathrm{Q}(f))$, so $\lambda$ lower-bounds quantum query complexity.
- 2026: $\mathrm{bs}(f)$ can exceed $\lambda(f)^2$ -- there is a total $f$ with $\mathrm{bs}(f)\ge\lambda(f)^{2.127}$ [Meiburg26], refuting an ABKRT question. Best upper bound remains $\mathrm{bs} = O(\lambda^4)$.
- The single-bit private-coin certificate game value equals $\lambda(f)^2$ [CGLMSG23].
- On a promise $\lambda$ is not weak but empty: if no two promise inputs are adjacent the sensitivity graph has no edges at all, so $\lambda = 0$ while $\mathrm{D} = \Theta(n)$ (\(\mathrm{forr}\), \(\mathrm{GapMaj}^{\delta}_{n}\)). The collapse is sharper than for $\mathrm{Adv}$, which merely drops to $\Theta(1)$ there: an exact $0$ kills every candidate bound $M \le g(\lambda)$ at once, since it would read $M \le g(0)$.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\lambda(f)\). “\(\lambda(f)\) in terms of it” is the pair with \(\lambda(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\sqrt{n}\) | Sensitivity graph is a star $K_{1,n}$ plus isolated edges; $\|K_{1,n}\| = \sqrt n$. ABKRT21 |
| AND total | \(\sqrt{n}\) | IJKKKSWW23 |
| PARITY total | \(n\) | Sensitivity graph is the whole hypercube, which is $n$-regular. |
| MAJORITY total | \((n+1)/2\) | The sensitivity graph is the middle-layer bipartite graph, which is $\tfrac{n+1}{2}$-regular, so $\lambda = \mathrm{s}$. |
| Threshold total | \(\sqrt{k(n-k+1)}\) putative | The sensitivity graph is exactly the bipartite graph between Hamming layers $k-1$ and $k$ of the cube: it is biregular of degrees $n-k+1$ (from the $k-1$ side) and $k$ (from the $k$ side), and a connected biregular bipartite graph has spectral norm $\sqrt{d_0 d_1}$ -- put $a$ on one side and $b$ on the other, so that $(n-k+1)b = \lambda a$ and $ka = \lambda b$. Recovers $\lambda(\mathrm{MAJ}) = (n+1)/2$ and $\lambda(\mathrm{OR}) = \sqrt n$, and it is exactly $\sqrt{\mathrm{C}^0\mathrm{C}^1}$, so [Huang19]'s $\deg \le \lambda^2$ is tight here only at the two ends. |
| Symmetric functions (general) total | \(\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$. |
| EXACT-HALF total | \(\sqrt{n(n/2+1)}\) putative | Exactly, and for $\mathrm{EH}_n$ itself (spectral sensitivity is insensitive to negation, since $f$ and $\bar f$ have the same sensitivity graph, so the same number is also $\lambda(\overline{\mathrm{EH}}_n)$). The sensitivity graph has an edge $(x,x^{\oplus i})$ exactly when one endpoint has weight $n/2$, so it is bipartite between the middle layer and the two layers $n/2\pm1$. It is biregular: a middle vertex has degree $n$, and a vertex of weight $n/2-1$ or $n/2+1$ has degree $n/2+1$. The vector giving $\sqrt n$ to each vertex of the second side and $\sqrt{n/2+1}$ to each middle vertex is positive with eigenvalue $\sqrt{n(n/2+1)}$, so by Perron--Frobenius that is the spectral radius. This meets the general bound $\lambda(f)\le\sqrt{\mathrm{s}^0(f)\,\mathrm{s}^1(f)}$ with equality, since $\mathrm{s}^1 = n$ and $\mathrm{s}^0 = n/2+1$ -- so $\mathrm{EH}$ is an exact witness for that inequality, and $\lambda = n/\sqrt2\,(1+o(1))$ sits strictly between the two. ABKRT21 |
| ODD-MAX-BIT total | \(\Theta(\sqrt n)\) | Sandwiched: $\sqrt{\mathrm{s}(f)} \le \lambda(f) = O(\mathrm{Q}_{\varepsilon}(f))$, with $\mathrm{s}(f) = \lfloor n/2\rfloor+1$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here. So \(\mathrm{OMB}_n\) joins \(\mathrm{OR}_n\) as a family where Huang's $\mathrm{s} \le \lambda^2$ is tight. ABKRT21 |
| ADDRESS / multiplexer total | \(\Theta(k)\) putative | Upper: $\lambda(f) \le \mathrm{s}(f) = k+1$. Lower: the spectral norm of a graph is at least its average degree, and the average degree of the sensitivity graph is exactly $\mathrm{I}(f) = (k+2)/2$. |
| Binary tree navigation total | \(\Theta(k)\) putative | Upper: $\lambda(f) \le \mathrm{s}(f) = k$. Lower: the spectral norm of a graph is at least its average degree, and the average degree of the sensitivity graph is exactly $\mathrm{I}(f) = (k+1)/2$. So $\lambda = \Theta(k)$, far above the $\sqrt{\deg} = \sqrt k$ floor of [Huang19]. |
| TRIBES total | \(\Theta(\sqrt n)\) | At most $\sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt{\Theta(n/\log n)\cdot\Theta(\log n)} = \Theta(\sqrt n)$, and at least $\sqrt{\deg} = \sqrt n$ by Huang. Huang19 ABKRT21 |
| AND-OR tree (depth 2) total | \(n\) | $\lambda$ is exactly multiplicative: $\lambda = \lambda(\mathrm{AND}_n)\lambda(\mathrm{OR}_n) = \sqrt n\cdot\sqrt n$. ABKRT21 |
| NAND tree (balanced AND-OR formula) total | \(\sqrt{N}\) | $\lambda(\mathrm{NAND}_2)=\sqrt2$ and $\lambda$ is multiplicative. |
| Recursive MAJORITY-of-3 total | \(2^d = N^{\log_3 2}\) | $\lambda(\mathrm{MAJ}_3)=2$, multiplicativity. |
| Kushilevitz's function (iterated) total | \(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 |
| Rubinstein's function total | \(\sqrt N = n\) putative | Pinned from both sides by the recorded chain $\sqrt{\deg} \le \lambda \le \mathrm{s}$: here $\deg = N$ and $\mathrm{s} = \sqrt N$ coincide at $\sqrt N$. Rubinstein's function is thus an extremal example for Huang's theorem in its spectral form. ABKRT21 |
| Ambainis-Sun function total | \(3k+2\) putative | Pinned exactly by $\sqrt{\deg} \le \lambda \le \mathrm{s}$ [ABKRT21]: $\deg = (3k+2)^2$ and $\mathrm{s} = 3k+2$. So $\mathrm{bs} = \tfrac23\lambda^2 - \tfrac13\lambda$ as well -- this function is also a near-extremal example for $\mathrm{bs}$ vs $\lambda$, the quantity later pushed past exponent $2$ by \(f_{\mathrm{Mei}}\). |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^{3/2})\) | $\lambda(\mathrm{AND}_n)\cdot\lambda(\overline{\mathrm{EH}}_n) = \sqrt n\cdot\Theta(n)$. IJKKKSWW23 |
| Meiburg's tournament-subcube function total | \(\le 89.0162^{\,d}\) | The base case is $\lambda \le 89.0162$ [Meiburg26]. Spectral sensitivity is exactly multiplicative under block composition [ABKRT21] -- the sensitivity-graph adjacency operator of $f\circ g$ is a tensor-like product -- so the family has $\lambda \le 89.0162^{\,d}$. Against the $\mathrm{bs}$ entry this gives $\mathrm{bs} \ge \lambda^{\log 14011/\log 89.0162} = \lambda^{2.127}$ for every $d$. Meiburg26 ABKRT21 |
| Pointer functions total | \(\widetilde O(n^{1/4})\) | Squeeze: $\lambda(f)=O(\widetilde{\deg}(f))$ [ABKRT21, Thms 17-18] applied to the line above. This is where the $\mathrm{D}=\widetilde\Omega(\lambda^4)$ entry of the $\lambda$ column comes from. ABKRT21 |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | Squeeze: $\lambda=O(\widetilde{\deg})$ [ABKRT21], with the floor $\lambda=\widetilde\Omega(\mathrm{D}^{1/6})$. ABKRT21 |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde O(n)\) | Squeeze: $\lambda\le\mathrm{s}=\widetilde O(n)$. Spectral sensitivity is therefore small here too, which is why this family also witnesses a large $\mathrm{D}$-vs-$\lambda$ gap. |
| Gilmer-Saks-Srinivasan functions total | \(O(n)\) | Squeeze: $\lambda\le\mathrm{s}=O(n)$, with the Huang floor $\lambda\ge\sqrt{\mathrm{s}}=\Omega(\sqrt n)$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde O(\sqrt n)\) | Squeeze: $\lambda=O(\widetilde{\deg})$ [ABKRT21]. Against $\mathrm{D}=\widetilde\Theta(n)$ this is another $\mathrm{D}=\widetilde\Omega(\lambda^2)$ family; the record is still the quartic one from \(g_{\mathrm{ABBLSS}}\). ABKRT21 |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | Squeeze: $\lambda=O(\widetilde{\deg})$ [ABKRT21]. ABKRT21 |
| Ambainis' exact-quantum function total | \(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. |
| FORRELATION partial | \(0\) putative | The sensitivity graph on the promise has no edges (see $\mathrm{s} = 0$), so the adjacency matrix is zero. Spectral sensitivity lower-bounds $\mathrm{Q}$ for total functions and says nothing at all here. |
| Simon's problem partial | \(0\) putative | Spectral sensitivity is at most sensitivity for partial $f$, and $\mathrm{s} = 0$ here: the sensitivity graph on the promise has no edges. So $\lambda = 0$ while $\mathrm{Q} = \Theta(n)$. |
| Deutsch-Jozsa partial | \(0\) putative | The sensitivity graph of $\mathrm{DJ}$ on its promise has no edges at all (see $\mathrm{s}=0$), so its adjacency matrix is zero. Spectral sensitivity, which for total functions satisfies $\deg \le \lambda^2$ and lower-bounds $\mathrm{Q}$, degenerates completely: $\lambda = 0$ while $\deg = 2$ and $\mathrm{D} = N/2+1$. |
| Bernstein-Vazirani partial | \(0\) putative | The sensitivity graph is empty (see $\mathrm{s} = 0$), so $\lambda = 0$ while $\mathrm{Q}_E = 1$ and $\mathrm{D} = n$. |
| Unique search partial | \(\sqrt n\) putative | The sensitivity graph is the star $K_{1,n}$ centred at $0^n$, whose adjacency matrix has spectral norm exactly $\sqrt n$. Both $\lambda \ge \sqrt{\mathrm{s}}$ and $\lambda = O(\mathrm{Q})$ are tight here. |
| Two-or-none search partial | \(0\) putative | The spectral norm of the empty graph. |
| Marked bit partial | \(0\) putative | The sensitivity graph is empty (see $\mathrm{s}$), so every bound of the form $M \le g(\lambda)$ fails here at once -- it would read $M \le g(0)$. |
| Dense marked bit partial | \(0\) | The sensitivity graph has no edges at all (see $\mathrm{s} = 0$), so its adjacency matrix is zero. |
| Gap-Majority partial | \(0\) putative | The sensitivity graph on the promise has no edges at all (see $\mathrm{s}=0$), so $\lambda = 0$ while $\deg = \Theta(n)$. Huang's theorem $\deg \le \lambda^2$ is a total-function statement and $\mathrm{GapMaj}$ breaks it as badly as arithmetic allows. |
| Gap-Majority at constant gap partial | \(0\) putative | The sensitivity graph on the promise has no edges, so $\lambda = 0$ while $\deg = \Theta(n)$. Huang's $\deg \le \lambda^2$ is a total-function theorem and this breaks it as badly as arithmetic allows. |
| Parity-labelled FIND-1 partial | \(0\) putative | The sensitivity graph is empty (see $\mathrm{s}$), so its spectral norm is $0$. |
| Approximate index partial | \(0\) putative | The sensitivity graph on the promise is empty (see $\mathrm{s} = 0$). |
| Collision problem partial | \(0\) putative | The sensitivity graph on the promise is empty (see $\mathrm{s} = 0$: no single change of the table stays inside the promise), so $\lambda = 0$ while $\mathrm{Q} = \Theta(n^{1/3})$. Huang's $\deg \le \lambda^2$ is a total-function theorem. |
| Element distinctness total | \(\Theta(\sqrt n)\) putative | Take the sensitivity graph on the Hamming graph of $\Sigma^n$. Restricting to the subcube $x_i \in \{0,i\}$ of the \(\deg(f)\) entry keeps single-symbol changes adjacent, so the restricted sensitivity matrix is a principal submatrix and $\lambda(\mathrm{ED}_n) \ge \lambda(\lnot\mathrm{Th}^n_2) \ge \sqrt{\deg(\lnot\mathrm{Th}^n_2)} = \sqrt n$ by [Huang19], which applies because the restriction is a total Boolean function. Above, $\lambda \le \mathrm{Adv} = O(\sqrt n)$. Huang19 |
| Ambainis-Belovs function partial | \(O(1)\) | $\lambda \le \mathrm{Adv} = O(\deg^2) = O(1)$. Spectral sensitivity, like every other measure bounded by the positive adversary, cannot see the $\Omega(n^{1/3})$ lower bound. |
| Surjectivity total | \(\Omega(\sqrt n),\ O(n/\sqrt{\log n})\) putative | Lower: $\lambda \ge \sqrt{\mathrm{s}} = \Omega(\sqrt n)$ -- a star of degree $\mathrm{s}$ sits inside the sensitivity graph -- which here is the same bound Huang's $\lambda \ge \sqrt{\deg}$ gives, since $\deg = n$. Upper: the sensitivity graph is bipartite between $0$- and $1$-inputs with side degrees $\mathrm{s}^0$ and $\mathrm{s}^1$, so $\lambda \le \sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt{\Theta(n/\log n)\cdot\Theta(n)} = O(n/\sqrt{\log n})$ -- the same ceiling the certificate barrier puts on $\mathrm{Adv}$, and for the same asymmetry reason. Which end is the truth is open. |
| Triangle finding total | \(\Theta(m)\) putative | Squeezed: $\sqrt{\mathrm{s}(f)} \le \lambda(f) \le \mathrm{Adv}(f)$, with $\mathrm{s} = \Theta(m^2)$ and $\mathrm{Adv} = \Theta(m)$. Spectral sensitivity is therefore a tight certificate that the positive adversary cannot go past $m$ here. |
| Recursive Fourier sampling partial | \(0\) | The sensitivity graph is empty, since $\mathrm{s} = 0$: there is not a single pair of legal oracles at Hamming distance one with different answers. So $\lambda(f) = 0$, and the $\mathrm{Q} = \Omega(\lambda)$ route -- like every other combinatorial route -- says nothing at all here. This is the case the \(\lambda(f)\) page's partial-setting warning is about. |
| Ordered search partial | \(\Theta(1)\) putative | Exactly $2\cos\!\big(\tfrac{\pi}{n+2}\big)$, which climbs to $2$ and never reaches it -- a constant, and that is the whole content: the sensitivity graph is a path. Its vertices are the $n+1$ promise inputs $0^k1^{n-k}$; two of them are Hamming neighbours exactly when their indices differ by one, and then the answers differ too, so $G_f = P_{n+1}$, whose adjacency matrix has spectral norm $2\cos(\pi/(n+2)) < 2$. Against $\mathrm{Q} = \Theta(\log n)$ this is the sharpest cheap illustration that spectral sensitivity is worthless on a promise: $\mathrm{Q} = \Omega(\lambda)$ gives nothing, and Huang's $\deg \le \lambda^2$ is vacuous here because $\deg = 1$ as well. |
| Inner product mod 2 total | \(n/\sqrt2\) | Write $\mathrm{IP}_n = \mathrm{PARITY}_{m} \circ \mathrm{AND}_2$ with $m = n/2$ and use exact multiplicativity of $\lambda$ [ABKRT21]: $\lambda = m \cdot \sqrt 2 = n/\sqrt2$. Consistent with $\sqrt{\mathrm{s}} \le \lambda \le \mathrm{s}$ at $\mathrm{s} = n$, and with $\mathrm{Q} = \Theta(n) = \Omega(\lambda)$; like \(\oplus_n\) and unlike \(\mathrm{AND}_n\), the inner product sits at the top of that range. |
| Minsky-Papert one-in-a-box total | \(m^{3/2} = \sqrt N\) | $\lambda$ is exactly multiplicative under block composition [ABKRT21], so $\lambda(\mathrm{AND}_m \circ \mathrm{OR}_{m^2}) = \sqrt m \cdot \sqrt{m^2} = m^{3/2}$. This matches $\mathrm{Q} = \Theta(\sqrt N)$ up to a constant -- spectral sensitivity is tight here, while it is a $\sqrt{\ }$-factor loose against $\mathrm{s} = m^2$. |
| Sink of a tournament total | \(\Theta(\sqrt m) = \Theta(N^{1/4})\) | Pinned from both sides. Upper: the sensitivity graph is bipartite with side-degrees at most $\mathrm{s}^0$ and $\mathrm{s}^1$, so $\lambda \le \sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt{3(m-1)}$. Lower: Huang's theorem in its spectral form gives $\lambda(f) \ge \sqrt{\deg(f)} = \sqrt{m-1}$. The two meet at $\Theta(\sqrt m)$. Note this is far below $\mathrm{s} = m-1$: SINK sits at the $\sqrt{\mathrm{s}}$ end of $\sqrt{\mathrm{s}} \le \lambda \le \mathrm{s}$, exactly like \(\mathrm{AND}_n\) and unlike \(\oplus_n\). |
| Scorpion graphs total | \(\Omega(\sqrt m),\ O(m)\) | Lower: Huang's theorem in spectral form, $\lambda \ge \sqrt{\deg} = \sqrt{3m-6}$. Upper: the sensitivity graph is bipartite with side-degrees $\mathrm{s}^1 = 3m-6$ and $\mathrm{s}^0 = 2m-4$, so $\lambda \le \sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt6\,(m-2)$. Not pinned; exhaustive computation gives $\lambda^2 = 16,\,23,\,26,\,33$ at $m = 4,\dots,7$, which tracks the $\Theta(\sqrt m)$ end. |
| Graph connectivity total | \(\Omega(m),\ O(m^{3/2})\) | Lower: $\lambda \ge \sqrt{\deg} = \sqrt{N} = \Theta(m)$ [Huang19]. Upper: $\lambda \le \sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt{\lfloor m^2/4\rfloor(m-1)} = \Theta(m^{3/2})$, far below $\mathrm{s} = \Theta(m^2)$. Exact diagonalisation of the sensitivity graph gives $\lambda = 2,\ 3.126,\ 4.356,\ 5.674$ at $m = 3,4,5,6$, i.e. $\lambda/m^{3/2} = 0.385,\ 0.391,\ 0.390,\ 0.386$ -- so the upper end looks like the truth, and $\lambda$ would then match $\mathrm{Q} = \Theta(m^{3/2})$ exactly. |