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

0-block sensitivity

Block sensitivity maximised only over 0-inputs.

Definition

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

Basic facts

  • $\mathrm{bs}(f) = \max(\mathrm{bs}^0(f), \mathrm{bs}^1(f))$ and $\mathrm{s}^0(f) \le \mathrm{bs}^0(f)$.
  • $\mathrm{C}^0(f) \le \mathrm{s}^1(f)\,\mathrm{bs}^0(f)$: a minimal sensitive block of a $0$-input has size at most $\mathrm{s}^1(f)$, and a maximal disjoint family of them is a certificate [Nisan91].
  • The one-sided quantities are what the $\mathrm{D} \le \mathrm{C}^0\mathrm{C}^1$-style bounds actually use, and they can be wildly asymmetric: $\mathrm{bs}^0(\mathrm{OR}_n) = n$ while $\mathrm{bs}^1(\mathrm{OR}_n) = 1$.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{bs}^0(f)\). “\(\mathrm{bs}^0(f)\) in terms of it” is the pair with \(\mathrm{bs}^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{bs}^0(f)\) in terms of it It in terms of \(\mathrm{bs}^0(f)\)
\(\mathrm{bs}(f)\) Block sensitivity total1,1 partial1,1 open pair → total∞ partial∞ open pair →
\(\mathrm{bs}^1(f)\) 1-block sensitivity total∞ partial∞ derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{s}^0(f)\) 0-sensitivity total∞ partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{C}^0(f)\) 0-certificate complexity total1,? partial1,? derived open pair → total∞ partial∞ 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\)
Threshold total \(n-k+1\)
EXACT-HALF total \(n/2 + 1\) Sandwiched: $\mathrm{s}^0(f) \le \mathrm{bs}^0(f) \le \mathrm{C}^0(f)$, with both ends $n/2+1$ here.
ODD-MAX-BIT total \(\lceil n/2 \rceil\) putative Equal to $\mathrm{s}^0$: blocks buy nothing on either side, by the maximum-index charging argument used for $\mathrm{bs}$. (Verified exhaustively for $n \le 12$.)
ADDRESS / multiplexer total \(k+1\) Squeezed between $\mathrm{s}^0 = k+1$ and $\mathrm{bs} = k+1$.
Binary tree navigation total \(k\) Squeezed between $\mathrm{s}^0 = k$ and $\mathrm{C}^0 = k$.
TRIBES total \(\Theta(n/\log n)\)
AND-OR tree (depth 2) total \(n\)
NAND tree (balanced AND-OR formula) total \(2^{\lceil d/2\rceil} = \Theta(\sqrt N)\) putative Sensitivity obeys the same recursion as certificate complexity here -- at a $0$-input every leaf that flips its own subtree is sensitive, giving $\mathrm{s}^0(f_d) = 2\,\mathrm{s}^1(f_{d-1})$, and at a $1$-input only the leaves of a single $0$-child can help, giving $\mathrm{s}^1(f_d) = \mathrm{s}^0(f_{d-1})$. So $\mathrm{s}^b = \mathrm{bs}^b = \mathrm{C}^b$ and the squeeze is tight on both sides.
Recursive MAJORITY-of-3 total \(2^d\) Between $\mathrm{s}^0 = 2^d$ and $\mathrm{bs} = 2^d$.
Kushilevitz's function (iterated) total \(N\) Between $\mathrm{s}^0 = N$ and the trivial ceiling $N$.
Rubinstein's function total \(N/2 = n^2/2\) putative This is where $\mathrm{bs} = \tfrac12\mathrm{s}^2$ comes from: at $0^N$ each of the $n$ blocks offers its $n/2$ adjacent pairs as disjoint sensitive blocks, so $\mathrm{bs}^0(f) = n\cdot\mathrm{bs}^0(g) = n\cdot n/2$, against $\mathrm{s}^0 = n$.
Ambainis-Sun function total \(6k^2+7k+2\) The value of \(\mathrm{bs}(f)\); $\mathrm{bs}^0(g) = 2k+1$ because disjoint sensitive blocks must switch on distinct patterns. AmbainisSun11
AND composed with NOT-EXACT-HALF total \(n = \sqrt N\) putative Every sensitive block of a $0$-input must repair every zero block, so it meets each of them and at most $n$ of them are disjoint; the $n$ singletons of a single zero block achieve it.
Meiburg's tournament-subcube function total \(14011^{\,d}\) putative Lower bound: [Meiburg26, Lemma 3.1] exhibits $14011$ disjoint sensitive blocks at the all-zeros input, which is a $0$-input, so $\mathrm{bs}^0 \ge 14011$ at $d=1$. Because the witnessing input is a $0$-input in every copy, the usual planting argument keeps the $0$-side: place the all-zeros input in every inner copy and take unions of inner blocks across each outer block, so $\mathrm{bs}^0(f^{\circ d}) \ge 14011^{\,d}$. Upper bound: $\mathrm{bs}^0 \le \mathrm{C}^0 \le 14011^{\,d}$ by \(\mathrm{C}^0(f)\). The two meet, so this is exact. Meiburg26
Pointer functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{bs}^0\le\mathrm{bs}=\widetilde O(\sqrt n)$ on variant $f_{2m,m}$. Against $\mathrm{D}=\widetilde\Omega(n)$ this alone is a quadratic $\mathrm{D}$-vs-$\mathrm{bs}^0$ gap. No floor is claimed: the natural candidate blocks (mark a whole column) are $m$ disjoint blocks but their sensitivity depends on the pointer conventions of the variant.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{bs}^0\le\mathrm{bs}=\widetilde O(\sqrt n)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3})\) putative Nisan's refined bound $\mathrm{C}^0\le\mathrm{s}_1\cdot\mathrm{bs}_0$ [Nisan91] with $\mathrm{C}^0=\widetilde\Theta(n^2)$ and $\mathrm{s}_1\le\mathrm{s}=\widetilde\Theta(n^{2/3})$. This pins the large block sensitivity to the $0$-side, matching the fact that $\mathrm{C}^0$ rather than $\mathrm{C}^1$ is what is large.
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) Squeeze: $\mathrm{s}_0\le\mathrm{bs}_0\le\mathrm{bs}=O(n)$.
Random-indicator gadget total \(\Theta(1)\) Ceiling $\mathrm{bs}^0 = O(1)$ [GSS16, Thm 32]. A sensitive block $B$ at a $0$-input $x$ means $x^B$ is a planted point, so two disjoint blocks give two planted points at Hamming distance exactly $|B_1|+|B_2|$; pairwise distance $\ge n/100$ therefore forces every pair of blocks to have total size $\ge n/100$, and disjoint blocks fit in $n$ coordinates, so there are at most $201$ of them. Floor $1$: a neighbour of a planted point is a $0$-input with a sensitive bit. GSS16
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) From the block-injection argument on the $\mathrm{bs}$ line: disjoint sensitive blocks at a $0$-input inject into the $k$ columns, so $\mathrm{bs}_0=O(k)=\widetilde O(\sqrt n)$. Combined with $\mathrm{C}^0=\widetilde\Theta(n)$ this is the extremal $\mathrm{C}^0=\widetilde\Omega(\mathrm{bs}_0^2)$ behaviour.
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) From the block-injection argument on the $\mathrm{bs}$ line: disjoint sensitive blocks at a $0$-input inject into the $k$ columns, so $\mathrm{bs}_0=O(k)$. Against $\mathrm{C}^0=\widetilde\Theta(n^{2/3})$ the $0$-side alone already realises the quadratic $\mathrm{C}$-vs-$\mathrm{bs}$ gap.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{s}_0\le\mathrm{bs}_0\le n$.
FORRELATION partial \(O(1)\) See $\mathrm{bs}$: $\mathrm{bs}^0 \le \mathrm{bs} = O(1)$.
k-FORRELATION partial \(O(k^2)\) See $\mathrm{bs}$.
Simon's problem partial \(2\) putative See $\mathrm{bs}$.
Deutsch-Jozsa partial \(2\) putative At $0^N$ the sensitive blocks are exactly the $N/2$-sized sets, and two disjoint ones fit.
Bernstein-Vazirani partial \(1\) At most $\mathrm{bs} = 1$, and at least $1$ at every input, since replacing the table by the codeword of any other secret is a sensitive block. So both one-sided values equal $1$ however the outputs are split into two classes.
Unique search partial \(n\) Only singleton blocks keep $0^n$ inside the promise, and all $n$ of them are sensitive.
Two-or-none search partial \(\lfloor n/2 \rfloor\) putative A block flipped at $0^n$ must land on the promise, so it is a pair, and $\lfloor n/2\rfloor$ disjoint pairs are available. Note $\mathrm{bs}^0 = \Theta(n)$ against $\mathrm{s}^0 = 0$: blocks survive the thickening, single bits do not.
Marked bit partial \(1\) putative See $\mathrm{bs}$.
Dense marked bit partial \(1\) See $\mathrm{bs}$.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) putative The count in $\mathrm{bs}$ is symmetric under complementation, so $\mathrm{bs}^0 = \mathrm{bs}^1 = \mathrm{bs}$: at an input of weight exactly $n/2-\delta n$, disjoint blocks of $2\delta n$ zeros each flip the answer, and no sensitive block is smaller.
Gap-Majority at constant gap partial \(1\) putative Symmetric under complementation; see $\mathrm{bs}$.
Parity-labelled FIND-1 partial \(1\) putative See $\mathrm{bs}$; the two sides are symmetric.
Approximate index partial \(1\) putative See $\mathrm{bs}$.
Collision problem partial \(2\) putative See $\mathrm{bs}$.
Element distinctness total \(2\) putative A block disjoint from the unique colliding pair cannot break the collision, so the two singletons $\{i\},\{j\}$ are all there is.
Ambainis-Belovs function partial \(O(1)\) Both sides are capped: $\mathrm{Adv} = \Omega(\sqrt{\mathrm{bs}^0\,\mathrm{bs}^1})$ and $\mathrm{bs}^0, \mathrm{bs}^1 \le \mathrm{bs} = O(1)$.
Surjectivity total \(\Theta(n/\log n)\) putative Upper: a sensitive block $B$ at a $0$-input must create every missing value, so fix one missing $u$ and map $B$ to the least slot $i$ with $(x\oplus B)_i = u$; two disjoint blocks cannot share that slot, since both would have to restrict to the same nonzero pattern $x_i \oplus u$ there. Hence $\mathrm{bs}^0 \le N$. Lower: $\mathrm{s}^0 = \Theta(N)$. So $\mathrm{bs}^0 = \Theta(N) = \Theta(n/\log n)$, and the block-sensitivity asymmetry matches the certificate asymmetry $\mathrm{C}^0 = N$ against $\mathrm{C}^1 = n/2$.
$k$-distinctness total \(\Theta(n)\) The $n-k+1$ singleton blocks of the $\mathrm{s}^0$ note are disjoint, and $\mathrm{bs}^0 \le n$.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}^0 \le \mathrm{bs}^0 \le \binom m2$, with $\mathrm{s}^0 = \Theta(m^2)$.
Recursive Fourier sampling partial \(1\) putative Both sides attain the recorded $\mathrm{bs} = 1$. Given any legal oracle $A$ and any $s'_\varnothing$ with $g(s'_\varnothing) \ne g(s_\varnothing)$, one can build a legal $A'$ realising it (choose the subtree secrets top-down), and $B = \{\text{leaves where } A \ne A'\}$ is a sensitive block; so $\mathrm{bs}_x \ge 1$ at every input, of either answer.
Ordered search partial \(2\) putative Same argument as $\mathrm{bs}$, at an interior $k$ of even parity.
Inner product mod 2 total \(\Theta(n)\) Between $\mathrm{s}^0 = \Theta(n)$ and $\mathrm{bs} = n$.
Minsky-Papert one-in-a-box total \(m^2 = N^{2/3}\) At a $0$-input with exactly one empty box, flipping any single bit of that box already makes the function $1$: $m^2$ disjoint singleton blocks.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) At least $m$: the out-edge sets of the $m$ vertices are disjoint, and flipping all of one vertex's out-edges makes it a sink. At most $\mathrm{bs} = O(m)$. This against $\mathrm{s}^0 = 3$ is the separation the $\mathrm{s}^0$ note describes.
Scorpion graphs total \(\Theta(m)\) Squeezed between $\mathrm{s}^0 = 2m-4$ and $\mathrm{C}^0 = \Theta(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Squeezed between $\mathrm{s}^0 = \lfloor m^2/4\rfloor$ and $\mathrm{C}^0 = \Theta(m^2)$.