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

0-sensitivity

Sensitivity maximised only over 0-inputs.

Definition

$\mathrm{s}^0(f) = \max_{x \in f^{-1}(0)} \mathrm{s}_x(f)$.

Basic facts

  • $\mathrm{s}(f) = \max(\mathrm{s}^0(f), \mathrm{s}^1(f))$.
  • $\lambda(f) \le \sqrt{\mathrm{s}^0(f)\,\mathrm{s}^1(f)}$.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{s}^0(f)\). “\(\mathrm{s}^0(f)\) in terms of it” is the pair with \(\mathrm{s}^0(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}^0(f)\) in terms of it It in terms of \(\mathrm{s}^0(f)\)
\(\mathrm{s}(f)\) Sensitivity total1,4 partial1,? derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{s}^1(f)\) 1-sensitivity total∞ partial∞ derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{bs}^0(f)\) 0-block sensitivity total1,1 partial1,1 open pair → total∞ partial∞ derived open pair →
\(\lambda(f)\) Spectral sensitivity total2,4 partial2,? derived open pair → total∞ partial∞ derived open pair →

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

Known values

FunctionValueNotes
OR total \(n\)
AND total \(1\)
PARITY total \(n\)
MAJORITY total \((n+1)/2\) At a $0$-input with exactly $(n-1)/2$ ones, each of the $(n+1)/2$ zeros is sensitive.
Threshold total \(n-k+1\) At an input with $k-1$ ones every zero is sensitive.
Symmetric functions (general) total \(\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)$.
EXACT-HALF total \(n/2 + 1\)
ODD-MAX-BIT total \(\lceil n/2 \rceil\) putative Attained at $0^n$: flipping position $j$ makes $j$ the highest $1$, which flips the answer exactly for the $\lceil n/2\rceil$ odd $j$. (Verified exhaustively for $n \le 12$.)
ADDRESS / multiplexer total \(k+1\) putative Take $y \equiv 0$ except $y_a = 0$ with all $2^k$ table entries chosen so that every address-neighbour of $a$ carries a $1$: then all $k$ address bits and $y_a$ itself are sensitive. Complementing the table swaps the two sides, so $\mathrm{s}^0 = \mathrm{s}^1$.
Binary tree navigation total \(k\) putative As $\mathrm{s}$: the construction there can be run with either final value, so both sides reach $k$. (Verified exhaustively for $k \le 3$.)
TRIBES total \(\Theta(n/\log n)\) Every tribe missing exactly one bit.
AND-OR tree (depth 2) total \(n\) putative Take one empty block and a single $1$ in each of the others: all $n$ bits of the empty block are sensitive, and nothing else is. Matches $\mathrm{s} = n$.
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt N)\) putative At a $b$-input of an alternating read-once formula the sensitive leaves are one per gate on the levels that force $b$, giving $2^{\lceil d/2\rceil}$ on one side and $2^{\lfloor d/2\rfloor}$ on the other. The two sides therefore differ by at most $\sqrt2$ and both are $\Theta(\sqrt N)$.
Recursive MAJORITY-of-3 total \(2^d\) putative Take the input in which every gate sees exactly two $0$-children; those two children are the sensitive ones, so the sensitive leaves double at each level. $\mathrm{MAJ}_3$ is self-dual, so the same works on the $1$-side.
Kushilevitz's function (iterated) total \(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.
Rubinstein's function total \(n = \sqrt N\) putative At a $0$-input the pivotal bits are those that make some block fire. A block at a weight-$1$ input has exactly one such bit (complete the pair), and no block state has more, so $\mathrm{s}^0(f) = n\cdot\mathrm{s}^0(g) = n$. Brute force on the gadget gives $\mathrm{s}^0(g) = 1$ for $n = 4,6,8$.
Ambainis-Sun function total \(3k+2\) Sensitivity of an OR of blocks is $n_{\mathrm{blocks}}\cdot\mathrm{s}^0$ of the gadget, and the Ambainis--Sun gadget has $\mathrm{s}^0(g) = 1$: two single-bit flips of a $0$-input landing in different patterns would put those patterns at Hamming distance $\le 2$, contradicting the distance-$3$ property. AmbainisSun11
AND composed with NOT-EXACT-HALF total \(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.
Pointer functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{s}^0\le\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$ on variant $f_{2m,m}$. The $\mathrm{s}=\widetilde\Theta(\sqrt n)$ pin comes entirely from the $1$-side (see the $\mathrm{s}^1$ line), so no matching floor is claimed for $\mathrm{s}^0$.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{s}^0\le\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$. Against $\mathrm{Q}=\widetilde\Theta(n)$ this alone is a quadratic $\mathrm{Q}$-vs-$\mathrm{s}^0$ gap.
Low-sensitivity function from unambiguous certificates total \(\widetilde O(n)\) Squeeze: $\mathrm{s}_0\le\mathrm{s}=\widetilde O(n)$. The desensitizing step is what makes both sides small: the inner $f'$ has $\mathrm{s}_0(f')\le 1$ by construction.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{s}_0\le\mathrm{s}=\widetilde\Theta(n^{2/3})$.
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) Squeeze: the $\mathrm{s}$ line above exhibits a $0$-input with $n$ sensitive blocks-of-size-one, and $\mathrm{s}_0\le\mathrm{s}=O(n)$.
Random-indicator gadget total \(\Theta(1)\) putative Squeeze: $1\le\mathrm{s}^0\le\mathrm{bs}^0=O(1)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{s}_0\le\mathrm{s}=\widetilde\Theta(\sqrt n)$; the $\mathrm{s}$ line above bounds it directly by $O(k\log k)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) Squeeze: $\mathrm{s}_0\le\mathrm{s}=\widetilde\Theta(n^{1/3})$; the $\mathrm{s}$ line bounds it directly by $O(k\log k)$.
Ambainis' exact-quantum function total \(3^d\) Squeeze: the all-zero input is fully sensitive, and $\mathrm{s}_0\le n$.
FORRELATION partial \(0\) putative See $\mathrm{s}$.
Simon's problem partial \(0\) putative See $\mathrm{s}$.
Deutsch-Jozsa partial \(0\) putative See $\mathrm{s}$: no single flip of a constant input stays in the promise.
Bernstein-Vazirani partial \(0\) Both halves inherit $\mathrm{s} = \max\{\mathrm{s}^0,\mathrm{s}^1\} = 0$: no single flip of a Hadamard codeword lands back in the promise.
Unique search partial \(n\) All $n$ neighbours of $0^n$ lie in the domain and are $1$-inputs.
Two-or-none search partial \(0\) putative The neighbours of $0^n$ all have $|x| = 1$ and are off the promise.
Marked bit partial \(0\) putative See $\mathrm{s}$.
Dense marked bit partial \(0\) See $\mathrm{s}$.
Gap-Majority partial \(0\) putative See $\mathrm{s}$: identically zero on both sides, whenever $2\delta n > 1$.
Gap-Majority at constant gap partial \(0\) putative See $\mathrm{s}$.
Parity-labelled FIND-1 partial \(0\) putative See $\mathrm{s}$: no domain neighbours anywhere.
Approximate index partial \(0\) putative See $\mathrm{s}$.
Collision problem partial \(0\) putative See $\mathrm{s}$.
Element distinctness total \(2\) putative A $0$-input can only be fixed by one symbol change if it has exactly one colliding pair $\{i,j\}$ and is otherwise distinct, and then only $i$ and $j$ are sensitive; every other $0$-input is less sensitive still.
Ambainis-Belovs function partial \(O(1)\) At most $\mathrm{bs}^0 = O(1)$.
Surjectivity total \(\Theta(n/\log n)\) putative A factor $\log n$ below $\mathrm{s}^1$. Upper: at a $0$-input, a single flip can only change one slot, so it can only add one value to the range; hence exactly one value $u$ may be missing and each slot has at most one sensitive bit, giving $\mathrm{s}^0 \le N = \Theta(n/\log n)$. Lower: take $u = 0^r$, cover the $R-1-r$ values of Hamming weight $\ge 2$ with one slot each and fill the remaining $N-R+1+r$ slots with duplicated weight-one values; flipping the single $1$ of any of those slots produces $u$ and loses nothing. Exhaustive check at $R=4$, $N=8$: $\mathrm{s}^0 = 7 = N-R+1+r$.
$k$-distinctness total \(\Theta(n)\) putative On the $0$-input of the $\mathrm{C}^0$ note, overwriting any of the $n-k+1$ positions outside the $(k-1)$-group with that group's symbol flips the answer. So the sensitivity is wildly asymmetric: $\Theta(n)$ on $0$-inputs against $k$ on $1$-inputs.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) putative The maximum in the $\mathrm{s}$ entry is attained at the $0$-input $K_{\lceil m/2\rceil,\lfloor m/2\rfloor}$, so it is the $0$-side that carries it.
Recursive Fourier sampling partial \(0\) Immediate from $\mathrm{s} = \max(\mathrm{s}^0,\mathrm{s}^1) = 0$.
Ordered search partial \(2\) putative Attained at any interior $k$ of even parity, $n \ge 3$.
Inner product mod 2 total \(\Theta(n)\) putative From $\mathrm{s}(x,y) = |x|+|y|$: the maximum $n$ is only at $x=y=1^m$ (value $m \bmod 2$) and the other side tops out at $n-1$. So $\{\mathrm{s}^0,\mathrm{s}^1\} = \{n, n-1\}$.
Minsky-Papert one-in-a-box total \(m^2\) As above.
Sink of a tournament total \(3\) Stated for $m \ge 3$. At a $0$-input, flipping the edge $e$ creates a sink iff $e$ is the unique out-edge of some vertex. Distinct vertices have distinct unique out-edges, so $\mathrm{s}^0_x$ counts the vertices of out-degree exactly $1$; if there are $k$ of them, the sub-tournament they span has $\binom k2$ edges and contributes $\binom k2$ to their out-degrees, whence $\binom k2 \le k$ and $k \le 3$. Three is attained: orient $u_1 \to u_2 \to u_3 \to u_1$ and every other edge into $\{u_1,u_2,u_3\}$. So $\mathrm{s}^0 = 3$ -- a constant, against $\mathrm{bs}^0 \ge m$ (the out-edge sets of the $m$ vertices are disjoint blocks, and flipping one makes its vertex a sink). SINK is thus a clean natural witness to a quadratic-and-then-some $\mathrm{s}^0$-versus-$\mathrm{bs}^0$ gap.
Scorpion graphs total \(2m-4\) putative The extremal $0$-input is $K_{m-2} \sqcup K_2$: a clique on $A$, plus a lone edge $\{u,v\}$ with no edges to $A$. Adding $ua$ for any $a \in A$ makes a scorpion with sting $v$, tail $u$, body $a$ (the clique makes $a$ dominate everything but $v$); symmetrically for $va$. That is $2(m-2)$ sensitive pairs, and exhaustive search confirms $\mathrm{s}^0 = 2m-4$ exactly for $m \le 7$. Contrast $\mathrm{s}^1 = 3m-6$: the scorpion is mildly $1$-biased.
Graph connectivity total \(\lfloor m^2/4 \rfloor\) putative At a disconnected $G$ the sensitive coordinates are exactly the absent pairs whose insertion connects the whole graph, so $G$ must have precisely two components and every crossing pair is sensitive. Balancing them gives $\lfloor m/2\rfloor\lceil m/2\rceil$. Deleting an edge from a disconnected graph never connects it, so nothing else contributes.