Q The Query Complexity Zoo
\(\mathrm{s}(f)\)

Sensitivity

Max over inputs of the number of coordinates whose flip changes the output.

also written: critical complexity, maximum sensitivity

Definition

For $x$ in the domain, $\mathrm{s}_x(f) = |\{ i : f(x) \neq f(x^{\oplus i}) \}|$ where $x^{\oplus i}$ flips coordinate $i$. Then $$\mathrm{s}(f) = \max_x \mathrm{s}_x(f), \qquad \mathrm{s}^b(f) = \max_{x \in f^{-1}(b)} \mathrm{s}_x(f).$$ Average sensitivity $\mathbb{E}_x[\mathrm{s}_x(f)]$ is the total influence $\mathrm{I}(f)$ (see \(\mathrm{I}(f)\)).

Basic facts

  • $\mathrm{s}(f) \le \mathrm{bs}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$.
  • Huang's theorem: $\deg(f) \le \mathrm{s}(f)^2$, hence $\mathrm{D}(f) = O(\mathrm{s}(f)^6)$ and all measures are polynomially related to $\mathrm{s}$ (for total $f$).
  • $\mathrm{s}(f) \ge \tfrac{1}{2}(\log_2 n - \log_2\log_2 n)$ for total $f$ depending on all $n$ variables.
  • For monotone $f$: $\mathrm{s}(f) = \mathrm{bs}(f) = \mathrm{C}(f)$.
  • On a promise the collapse is total, not merely polynomial. \(\mathrm{forr}\), \(\mathrm{GapMaj}^{\delta}_{n}\) and \(\mathrm{TSAT}_n\) have no two promise inputs at Hamming distance $1$, so $\mathrm{s} = 0$ while $\mathrm{D} = \Theta(n)$. A candidate bound $M \le g(\mathrm{s})$ would then read $M \le g(0)$, a single number, so no function $g$ works: every column of the matrix reads $\infty$ against $\mathrm{s}$ in the partial setting.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{s}(f)\). “\(\mathrm{s}(f)\) in terms of it” is the pair with \(\mathrm{s}(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.

Other measure \(\mathrm{s}(f)\) in terms of it It in terms of \(\mathrm{s}(f)\)
\(\mathrm{bs}(f)\) Block sensitivity total1,1 partial1,1 open pair → total2.1308,4 partial∞ open pair →
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 open pair → total3,5 partial∞ open pair →
\(\deg(f)\) Exact degree total1.63,2 partial∞ open pair → total2,2 partial∞ open pair →
\(\lambda(f)\) Spectral sensitivity total2,2 partial2,2 open pair → total1,1 partial1,1 open pair →
\(\mathrm{s}^0(f)\) 0-sensitivity total∞ partial∞ derived open pair → total1,4 partial1,? derived open pair →
\(\mathrm{s}^1(f)\) 1-sensitivity total∞ partial∞ derived open pair → total1,4 partial1,? derived open pair →

The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(n\)
AND total \(n\)
PARITY total \(n\)
MAJORITY total \((n+1)/2\)
Threshold total \(\max\{k,\; n-k+1\}\)
Symmetric functions (general) total \(\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)$.
EXACT-HALF total \(n\)
ODD-MAX-BIT total \(\lfloor n/2 \rfloor + 1\) putative Coordinates below the highest $1$ are never sensitive, so at an input whose highest $1$ is at position $i$ only position $i$ and the opposite-parity positions above it can be sensitive: $\mathrm{s}(x) \le 1 + \lceil (n-i)/2\rceil$. The bound is met at $x=e_1$, where $\{1\}\cup\{j>1 : j \text{ even}\}$ is sensitive.
ADDRESS / multiplexer total \(k+1\)
Binary tree navigation total \(k\) putative At the right input all $k$ walk variables are sensitive: flipping the bottom one flips the output, and flipping the one at level $j$ diverts the walk into the sibling subtree -- arrange each sibling subtree to deliver the opposite bit. Nothing off the walk is sensitive.
TRIBES total \(\Theta(n/\log n)\)
AND-OR tree (depth 2) total \(n = \sqrt N\)
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\)
Recursive MAJORITY-of-3 total \(2^d = N^{0.6309}\)
Kushilevitz's function (iterated) total \(N = 6^k\)
Rubinstein's function total \(n = \sqrt N\) Achieved at an input where each block has a single $1$ in an odd position.
Ambainis-Sun function total \(3k+2\) Both sides agree: $\mathrm{s}^0(f) = (3k+2)\mathrm{s}^0(g) = 3k+2$ and $\mathrm{s}^1(f) = \mathrm{s}^1(g) = 3k+2$. Balancing them is exactly how the number of blocks was chosen. AmbainisSun11
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) IJKKKSWW23
Meiburg's tournament-subcube function total \(\Omega(10.87^{\,d})\) putative Chain the two directions of the degree: $\mathrm{bs} = O(\deg^2)$ [NS94] gives $\deg = \Omega(\sqrt{\mathrm{bs}})$, and $\mathrm{s} \ge \sqrt{\deg}$ [Huang19] then gives $\mathrm{s} = \Omega(\mathrm{bs}^{1/4}) = \Omega(14011^{\,d/4})$. Sensitivity of this family is therefore not pinned: anywhere from $\mathrm{bs}^{1/4}$ to $\mathrm{bs}$ is consistent with what is proved, and $\lambda \le \mathrm{s}$ says nothing here because only an upper bound on $\lambda$ is known. Huang19 NS94
Pointer functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$ on variant $f_{2m,m}$; Huang gives the floor $\mathrm{s}\ge\sqrt{\mathrm{bs}}=\widetilde\Omega(n^{1/4})$.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$, with the Huang floor $\mathrm{s}\ge\sqrt{\mathrm{bs}}=\widetilde\Omega(n^{1/4})$.
Low-sensitivity function from unambiguous certificates total \(\widetilde O(n)\) Every sensitive bit of $\hat f = \mathrm{BSum}_n\circ f'$ lies in a block that is sensitive for the outer Block $k$-sum, and Block $k$-sum has certificates containing only $O(\log^3 n)$ ones; with $\mathrm{s}_0(f')\le 1$ this gives $\mathrm{s}(\hat f)\le n\,\mathrm{s}_0(f')+O(\log^3 n)\,\mathrm{s}_1(f')=\widetilde O(n)$ [BHT17, Thm 3]. BHT17
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Theta(n^{2/3})\) The recorded witness is $\mathrm{C}=\widetilde\Omega(\mathrm{s}^3)$ with $\mathrm{C}=\widetilde\Theta(n^2)$, which gives $\mathrm{s}=\widetilde O(n^{2/3})$; and the separation is only the recorded $\mathrm{C}$-vs-$\mathrm{s}$ exponent if $\mathrm{s}$ is no smaller, so $\widetilde\Theta$. (The tempting shortcut $\mathrm{C}\le\mathrm{s}\cdot\mathrm{bs}\le\mathrm{s}^3$ is not available: $\mathrm{bs}\le\mathrm{s}^2$ is the conjecture; what [Huang19] proves is $\mathrm{bs}\le\mathrm{s}^4$.) BBGJK21
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) putative Upper $\mathrm{s}\le\mathrm{bs}=O(n)$. Lower: take a point $y$ at Hamming distance $1$ from some $x^i$, so $\mathrm{s}_y(g_n)=1$, and feed the copy $(y,\dots,y)$ to $\mathrm{OR}_n\circ g_n$; every one of the $n$ blocks is then sensitive, so $\mathrm{s}_0(f)\ge n$.
Random-indicator gadget total \(n\) Squeeze: $\mathrm{s}=\max\{\mathrm{s}^0,\mathrm{s}^1\}=n$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(\sqrt n)\) putative Lower: at a $1$-input with a unique witness column, all $k$ cells of that column are sensitive. Upper: $\mathrm{s}_1\le\mathrm{C}_1=\widetilde O(\sqrt n)$, and at a $0$-input a sensitive bit must single-handedly create a witness column, so it is either the target bit of one of the $k$ columns or one of the $O(\log k)$ pointer bits redirecting a column at an existing $0$, giving $\mathrm{s}_0=O(k\log k)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{1/3})\) putative Lower: at a $1$-input with a unique witness column, all $k$ bits of that column are sensitive. Upper: $\mathrm{s}_1\le\mathrm{C}_1=\widetilde O(n^{1/3})$; at a $0$-input a single flip must create a witness column, and per column only the unique missing $1$, the unique non-zero target, or the $O(\log k)$ bits of the list entry addressing it can do that, so $\mathrm{s}_0=O(k\log k)$.
Ambainis' exact-quantum function total \(3^d\) Same all-zero input: $\mathrm{s}_0 = 3^d$, and $\mathrm{s}\le n = 3^d$. This is what forces $\mathrm{D}$ and $\mathrm{R}$ to be maximal. Ambainis13
FORRELATION partial \(0\) putative The promise gap is wider than one flip. Flipping a single $x_i$ changes $\Phi$ by $\tfrac{2}{n^{3/2}}\big|\sum_j (-1)^{i\cdot j} y_j\big| \le 2/\sqrt n$, and the same bound holds for a $y_j$; the two promise regions are separated by $3/5 - 1/100$. So for $n \ge 12$ no single flip stays inside the promise with a different value, and $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = \Theta(n)$.
Simon's problem partial \(0\) putative Counting a query as one evaluation of $g$, as everywhere in this entry. Changing $g$ at a single point never stays inside the promise: from an injective $g$ it can create at most one collision, and a two-to-one function needs all $2^{n-1}$ pairs to collide; from a two-to-one $g$ it orphans exactly one pair, leaving a function that is neither injective nor two-to-one. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ against $\mathrm{D} = \Theta(2^{n/2})$.
Deutsch-Jozsa partial \(0\) putative For $N \ge 4$ no single flip stays inside the promise: a constant input becomes weight $1$ or $N-1$, a balanced one weight $N/2 \pm 1$. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = N/2+1$. The extreme illustration of why sensitivity says nothing about partial functions.
Bernstein-Vazirani partial \(0\) putative The promise inputs are exactly the $2^n$ codewords of the Hadamard code, and two distinct codewords differ in $2^{n-1} \ge 2$ positions. So no single flip stays inside the promise and $\mathrm{s} = 0$, against $\mathrm{D} = n$.
Unique search partial \(n\)
Two-or-none search partial \(0\) putative Any two domain points differ in at least two coordinates, so the sensitivity graph is edgeless. This is the entire point of the function: it is \(\mathrm{SEARCH}^{\le 1}_n\) with the distance-$1$ pairs deleted from the domain, and deleting them costs nothing quantumly.
Marked bit partial \(0\) putative No single flip stays on the promise while changing the answer. Adding a mark of the same colour or removing one of several leaves the value alone; removing the last mark, or adding a mark of the other colour, or setting a cell's two encoding bits to $11$, all leave the domain. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ and the sensitivity graph has no edges at all.
Dense marked bit partial \(0\) putative No promise-preserving single flip changes the answer. From a $1$-input, setting some $y_b$ to $1$ keeps the answer $1$; clearing a $y_b$ either keeps it $1$ or drops below $n/2$ marks and leaves the promise; and setting any $z_b$ to $1$ creates marks of both colours, also off the promise.
Gap-Majority partial \(0\) putative Whenever $2\delta n > 1$. A single flip moves $|x|$ by one, and the value only changes on crossing $n/2$, which the promise puts $2\delta n$ away; so the flipped input is either outside the promise or has the same value. Sensitivity is therefore identically zero while $\mathrm{bs} = \Theta(\min(n,1/\delta))$ and $\mathrm{D} = \Theta(n)$: the promise-function counterexample to every bound with $\mathrm{s}$ on the small side.
Gap-Majority at constant gap partial \(0\) putative A single flip moves $|x|$ by one and the promise puts the two sides $n/2$ apart, so no promise input has a sensitive coordinate at all.
Parity-labelled FIND-1 partial \(0\) putative Identically zero: a single flip changes $|x|$ to $n/4 \pm 1$ and leaves the promise, so the sensitivity graph on the domain has no edges at all. An exact-weight promise kills $\mathrm{s}$ the same way a gapped one does at \(\mathrm{GapMaj}^{\delta}_{n}\).
Approximate index partial \(0\) putative No single flip stays inside the promise. Flipping a bit of the address $a$ moves the ball, leaving cells inside the new ball holding $2$; flipping a bit of an array cell either breaks the "$v$ inside the ball" condition or the "$2$ outside" one. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$.
Collision problem partial \(0\) putative Counting a query as one evaluation of $g$. Changing $g$ at a single point never stays in the promise: from a one-to-one $g$ it creates at most one collision, while a two-to-one $g$ needs all $n/2$ pairs to collide; from a two-to-one $g$ it orphans exactly one pair. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = n/2+1$.
Element distinctness total \(n\) putative Counting a query as one symbol read. At an all-distinct input every one of the $n$ coordinates is sensitive: overwrite $x_i$ with $x_j$ for any $j \ne i$ and the answer flips. So $\mathrm{s} = n$, and unlike the promise problems in this file the total function \(\mathrm{ED}_n\) is as sensitive as it can be.
Ambainis-Belovs function partial \(O(1)\) $\mathrm{s} \le \mathrm{bs} = O(1)$.
Surjectivity total \(\Theta(n)\) putative At $R = N/2$ take the list in which each of $1,\dots,R-1$ occurs exactly once and $R$ fills the remaining $R+1$ slots: a $1$-input on which flipping any bit of any uniquely-occurring element deletes that value from the range, so $\mathrm{s} \ge (R-1)\log_2 R = n/2 - O(\log n)$. And $\mathrm{s}\le n$.
$k$-distinctness total \(\Theta(n)\) $\mathrm{s} = \max(\mathrm{s}^0,\mathrm{s}^1) = \Theta(n)$.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) putative On that same $K_{m/2,m/2}$ all $2\binom{\lfloor m/2\rfloor}{2} = \Theta(m^2)$ non-edges are sensitive, and $\mathrm{s} \le \binom m2$. Note the asymmetry: on a $1$-input with a single triangle and nothing else, $\mathrm{s} = 3$, so it is $\mathrm{s}^0$ that carries the maximum.
Recursive Fourier sampling partial \(0\) putative Exactly zero, and this is the sharpest illustration in the zoo of the warning on the \(\mathrm{s}(f)\) page that sensitivity is useless on a promise. Group the leaves by their parent $v$: the oracle restricted to the $2^n$ children of $v$ is the linear function $x \mapsto s_v\cdot x$, because the promise says $g(s_{vx}) = s_v\cdot x$. Changing a single leaf value destroys linearity, so no single-bit flip of a legal oracle is legal, and there is nothing for $\mathrm{s}$ to count. Compare $\mathrm{bs} = 1$: the smallest legal-to-legal change flips a $2^{-\ell}$ fraction of the whole tree.
Ordered search partial \(2\) putative Decision version, $n \ge 2$. Flipping bit $j$ of $0^k1^{n-k}$ leaves the promise unless $j \in \{k, k+1\}$, and those two flips move to $k-1$ and $k+1$, both of which change the parity. So $\mathrm{s}_x = 2$ in the interior and $1$ at $k \in \{0,n\}$. This is the measure's partial-setting warning made concrete: $\mathrm{s} = 2$ while $\mathrm{R} = \Theta(\log n)$. The certificate family is $\Theta(1)$ too -- $\{x_k = 0,\,x_{k+1} = 1\}$ pins $k$ among promise inputs, so $\mathrm{C} = \mathrm{C}^0 = \mathrm{C}^1 = 2$ and $\mathrm{C}_{\min} = 1$ -- but those cells are deliberately left blank, because the zoo's \(\mathrm{Adv}(f)\) vs \(\mathrm{C}(f)\) record (the certificate-complexity barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1}$) is a theorem about partial Boolean functions, whereas the $\mathrm{Adv}$ value recorded below is [ChildsLee08]'s exact bound for the $(n+1)$-valued search version. Those two coexisting -- $\mathrm{Adv} = \tfrac1\pi\ln n$ against $\mathrm{C} = 2$ -- is precisely the observation that the barrier does not survive a large output alphabet; on the Boolean version $\mathrm{OS}^{\oplus}_n$ the barrier does apply and forces $\mathrm{Adv} = O(1)$ despite $\mathrm{Q} = \tilde\Theta(\log n)$, which is why [BunVoronova23] had to go through approximate degree.
Inner product mod 2 total \(n\) Flipping $x_i$ changes the value iff $y_i = 1$, and symmetrically, so $\mathrm{s}(x,y) = |x| + |y|$; at $x = y = 1^m$ that is $n$.
Minsky-Papert one-in-a-box total \(m^2 = N^{2/3}\) One-sided. At a $1$-input only a box's unique $1$ is sensitive, so $\mathrm{s}^1 = m$; at a $0$-input with exactly one empty box, every one of that box's $m^2$ bits is sensitive, so $\mathrm{s}^0 = m^2$.
Sink of a tournament total \(m-1 = \Theta(\sqrt N)\) $\max\{\mathrm{s}^0,\mathrm{s}^1\} = \max\{3, m-1\}$.
Scorpion graphs total \(3m-6\) putative $\max(\mathrm{s}^0,\mathrm{s}^1) = \max(2m-4,\,3m-6)$.
Graph connectivity total \(\lfloor m^2/4 \rfloor = \Theta(N)\) putative The $0$-side wins by a full quadratic factor: two balanced cliques are as $0$-sensitive as a graph can be, while $1$-sensitivity is capped by the $m-1$ bridges of a tree.
Pabbaraju’s certificate–sensitivity separator total \(O(n)\) Appendix C: s(F)≤3u, u=Θ(n). Pabbaraju26
OpenAI’s nested tournament sensitivity separator total \(O(5843507755269244925453189084787151790243135958374678911440649158260034799828648025876463378968022^m)\) Corollary 4.3: sensitivity ≤A^m, A=22M¹⁰. OpenAISensitivity26
AND of complemented EXACT-ONE functions total \(m^2\) Every single-bit flip at zero creates an EXACT-ONE block. KLLPV26