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.
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\) | |
| 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)$. |