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

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.

Other measure \(\mathrm{s}^1(f)\) in terms of it It in terms of \(\mathrm{s}^1(f)\)
\(\mathrm{s}(f)\) Sensitivity total1,4 partial1,? derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{s}^0(f)\) 0-sensitivity total∞ partial∞ derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{bs}^1(f)\) 1-block sensitivity total1,1 partial1,1 open pair → total1,? partial1,? 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 \(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.