1-sensitivity
Sensitivity maximised only over 1-inputs.
Definition
$\mathrm{s}^1(f) = \max_{x \in f^{-1}(1)} \mathrm{s}_x(f)$.
Basic facts
- $\lambda(f) \le \sqrt{\mathrm{s}^0(f)\,\mathrm{s}^1(f)}$ [ABKRT21, Lemma 31].
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{s}^1(f)\). “\(\mathrm{s}^1(f)\) in terms of it” is the pair with \(\mathrm{s}^1(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 | \(1\) | |
| AND total | \(n\) | |
| PARITY total | \(n\) | |
| MAJORITY total | \((n+1)/2\) | |
| Threshold total | \(k\) | At an input with exactly $k$ ones every one is sensitive. |
| Symmetric functions (general) total | \(\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$. |
| EXACT-HALF total | \(n\) | |
| ODD-MAX-BIT total | \(\lfloor n/2 \rfloor + 1\) putative | Attained at $e_1$: the $\lfloor n/2 \rfloor$ even positions above, plus position $1$ itself. This is the value recorded as $\mathrm{s}$. |
| ADDRESS / multiplexer total | \(k+1\) putative | By the complement symmetry $\mathrm{ADDR}_k(a,\bar y) = 1 - \mathrm{ADDR}_k(a,y)$, the two sides are equal; see $\mathrm{s}^0$. |
| Binary tree navigation total | \(k\) putative | As $\mathrm{s}^0$. |
| TRIBES total | \(\Theta(\log n)\) | Flip any bit of the unique all-ones tribe. |
| AND-OR tree (depth 2) total | \(n\) putative | Take exactly one $1$ per block: those $n$ bits are sensitive. |
| NAND tree (balanced AND-OR formula) total | \(\Theta(\sqrt N)\) | As $\mathrm{s}^0$. |
| Recursive MAJORITY-of-3 total | \(2^d\) putative | As $\mathrm{s}^0$, by self-duality of $\mathrm{MAJ}_3$. |
| Kushilevitz's function (iterated) total | \(N\) putative | Mirror of $\mathrm{s}^0$: $K(1^6)=1$ (weight $6$ is a $1$-input, all six weight-$5$ neighbours are $0$-inputs), so the all-one input of $K^{\circ k}$ is fully sensitive as well. Kushilevitz's function is fully sensitive on both sides, which is what makes the $\mathrm{s}$-vs-$\deg$ separation survive negation. |
| Rubinstein's function total | \(n = \sqrt N\) putative | A $1$-input has a firing block; all $n$ of its bits are sensitive (each flip destroys the pattern) and no bit outside it is. If two blocks fire the input is not sensitive at all, so $\mathrm{s}^1(f) = \mathrm{s}^1(g) = n$. |
| Ambainis-Sun function total | \(3k+2\) | $\mathrm{s}^1(f) = \mathrm{s}^1(g)$ for an OR of blocks, and a $1$-input of $g$ satisfies exactly one pattern, whose $3k+2$ pinned bits are the only candidates for sensitivity -- all of them sensitive at $y = 110\cdots0$. AmbainisSun11 |
| AND composed with NOT-EXACT-HALF total | \(n^2/2 + n\) putative | At a $1$-input every block has weight $\ne n/2$, and a bit is pivotal exactly when its block sits at weight $n/2\pm1$ and the bit moves it to $n/2$; a block at weight $n/2\pm1$ has $n/2+1$ such bits. Taking all $n$ blocks there gives $\mathrm{s}^1 = n(n/2+1)$, which is the recorded $\mathrm{s} = \Theta(n^2)$. Brute force confirms $\mathrm{s}^1(\overline{\mathrm{EH}}_n) = n/2+1$ for $n \le 10$. |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$, a $2m\times m$ grid with $n=\widetilde\Theta(m^2)$ bits. Lower: a $1$-input has one all-marked column, and it is unique, so flipping the marked bit of any one of that column's $2m$ cells leaves no all-marked column at all and sends the value to $0$. That is $2m=\widetilde\Omega(\sqrt n)$ sensitive coordinates at a single input. Upper: $\mathrm{s}^1\le\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$. Combined with the recorded $\mathrm{s}$ line this pins $\mathrm{s}=\widetilde\Theta(\sqrt n)$: the pointer function is not a sensitivity separation, and all of its gaps against $\mathrm{D}$ live on the randomized/quantum side. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{s}^1\le\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$. No floor is claimed for either side separately; Huang's $\mathrm{s}\ge\sqrt{\mathrm{bs}}$ only bounds the two-sided maximum. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde O(n)\) | Squeeze: $\mathrm{s}_1\le\mathrm{s}=\widetilde O(n)$; the outer Block $k$-sum contributes only $O(\log^3 n)$ ones per certificate. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n^{2/3})\) | Squeeze: $\mathrm{s}_1\le\mathrm{s}=\widetilde\Theta(n^{2/3})$. |
| Gilmer-Saks-Srinivasan functions total | \(n\) putative | A $1$-input of $g_n$ is an isolated point, so all $n$ of its bits are sensitive; feeding it to one copy of $\mathrm{OR}_n\circ g_n$ with the other $n-1$ copies at $0$-inputs gives $\mathrm{s}_1(f)\ge n$. The ceiling is $\mathrm{s}_1\le\mathrm{C}^1=n$. |
| Random-indicator gadget total | \(n\) putative | Every neighbour of an isolated planted point is a $0$-input. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Theta(\sqrt n)\) putative | Lower: at a $1$-input with a unique witness column all $k=\widetilde\Theta(\sqrt n)$ cells of that column are sensitive. Upper: $\mathrm{s}_1\le\mathrm{C}^1=\widetilde O(\sqrt n)$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Theta(n^{1/3})\) putative | Lower: at a $1$-input with a unique witness column all $k=\widetilde\Theta(n^{1/3})$ bits of that column are sensitive. Upper: $\mathrm{s}_1\le\mathrm{C}^1=\widetilde O(n^{1/3})$. |
| Ambainis' exact-quantum function total | \(3^{d-1}\) putative | Exact. At a $1$-input of $\mathrm{NE}$ exactly one of the three coordinates is sensitive -- the odd one out, e.g. only $y_1$ at $y=011$ -- so $\mathrm{s}_1(\mathrm{NE}^d)=\max\{\mathrm{s}_0,\mathrm{s}_1\}(\mathrm{NE}^{d-1})=\mathrm{s}_0(\mathrm{NE}^{d-1})=3^{d-1}$, attained by putting the all-zero input into one child and $1$-inputs into the other two. So the fully sensitive input is essentially unique to the $0$-side: $\mathrm{s}_1$ is a factor $3$ below $\mathrm{s}_0=3^d$. |
| FORRELATION partial | \(0\) putative | See $\mathrm{s}$. |
| Simon's problem partial | \(0\) putative | See $\mathrm{s}$. |
| Deutsch-Jozsa partial | \(0\) putative | See $\mathrm{s}$: flipping one bit of a balanced input gives weight $N/2 \pm 1$, outside the promise. |
| Bernstein-Vazirani partial | \(0\) | As for $\mathrm{s}^0$. |
| Unique search partial | \(1\) | The only domain neighbour of $e_i$ is $0^n$; flipping any other coordinate leaves the promise. |
| Two-or-none search partial | \(0\) putative | The neighbours of a weight-$2$ point have weight $1$ or $3$. |
| 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 | \(n\) putative | At an all-distinct input, overwriting $x_i$ with $x_j$ flips the answer for every $i$. |
| Ambainis-Belovs function partial | \(O(1)\) | At most $\mathrm{bs}^1 = O(1)$. |
| Surjectivity total | \(\Theta(n)\) putative | The $\mathrm{s} = \Theta(n)$ witness on this page is a $1$-input, so the maximum is carried by the $1$-side: $\mathrm{s}^1 \ge (R-1)\log_2 R = n/2 - O(\log n)$. Exhaustive check at $R=4$, $N=8$: $\mathrm{s}^1 = 6 = (R-1)\log_2 R$. |
| $k$-distinctness total | \(k\) putative | At a $1$-input every sensitive position must destroy every $k$-fold repeat, so it lies in all of them; a $1$-input with a single $k$-group therefore has sensitivity exactly $k$, and no $1$-input has more. The same argument caps $\mathrm{bs}^1$. |
| Triangle finding total | \(3\) putative | Sharp, and the whole story of this problem in one line. If two edges $e \ne f$ are both sensitive at a $1$-input then deleting either kills every triangle, so every triangle contains both; four sensitive edges are impossible and three must be a single triangle. Attained by a graph with exactly one triangle. Compare $\mathrm{s}^0 = \Theta(m^2)$. |
| 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 odd parity, $n \ge 3$. |
| Inner product mod 2 total | \(\Theta(n)\) putative | See $\mathrm{s}^0$. |
| Minsky-Papert one-in-a-box total | \(m\) | As above. |
| Sink of a tournament total | \(m-1\) | Stated for $m \ge 5$. At a $1$-input the sink $v$ is unique, and flipping an edge not incident to $v$ leaves $v$ a sink, so only the $m-1$ edges at $v$ can be sensitive. Flipping $u \to v$ fails to be sensitive only if $u$ then becomes a sink, i.e. only if $u \to v$ was $u$'s only out-edge -- and at most one such $u$ can exist, since two of them would need an edge between them. So $\mathrm{s}^1 \in \{m-2, m-1\}$, and $m-1$ is attained by any $1$-input in which every non-sink has out-degree $\ge 2$ (e.g. a near-regular tournament on $V \setminus \{v\}$ with every vertex pointing at $v$), which exists for $m \ge 5$. |
| Scorpion graphs total | \(3m-6\) putative | Take the scorpion with independent feet. The pairs touching $\{s,t,b\}$ number $3 + 3(m-3) = 3m-6$, and each of them is sensitive: adding an edge at the sting or the tail destroys the only degree-$1$/degree-$2$ pair, deleting $st$ or $tb$ breaks the chain, and deleting a body-foot edge stops $b$ from dominating -- in every case no other triple can take over, because a replacement sting would need a neighbour of degree $2$ and the only such vertex is gone. Pairs between feet are insensitive by definition. Exhaustive search confirms $\mathrm{s}^1 = 3m-6$ exactly for $m \le 7$. |
| Graph connectivity total | \(m-1\) putative | At a connected $G$ the sensitive coordinates are exactly the bridges -- adding an edge can never disconnect. A tree has $m-1$ bridges and nothing has more. |