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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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. |