Block sensitivity
Max number of disjoint blocks of coordinates each of whose flips changes the output.
Definition
$\mathrm{bs}_x(f)$ is the maximum number of pairwise disjoint sets $B_1,\dots,B_k \subseteq [n]$ with $f(x^{\oplus B_j}) \ne f(x)$ for all $j$; $\mathrm{bs}(f) = \max_x \mathrm{bs}_x(f)$, and $\mathrm{bs}^b$ restricts to $f^{-1}(b)$. Restricting to singleton blocks recovers sensitivity. The $\ell$-bounded variant $\mathrm{bs}_\ell$ requires $|B_j| \le \ell$.
Basic facts
- $\mathrm{bs}(f) \le \mathrm{D}(f)$ and $\mathrm{bs}(f) \le 3\,\mathrm{R}(f)$ [Nisan].
- $\mathrm{bs}(f) \le 2\deg(f)^2$ and $\mathrm{bs}(f) \le 6\widetilde{\deg}(f)^2$ [Nisan-Szegedy].
- $\mathrm{bs}(f) = O(\mathrm{Q}(f)^2)$.
- $\mathrm{bs}_\ell(f) = O(\mathrm{s}(f)^\ell)$ [Kenyon-Kutin].
- Whether $\mathrm{D}(f) = O(\mathrm{bs}(f)^2)$ is a long-standing open problem.
- Universal quadratic bounds are false: [OpenAISensitivity26] give a fixed separation exponent $\alpha>2$. The public Prove2Me theorem improves the lower endpoint to $\alpha=\log(14055^8)/\log(3738277295413674)=2.1308255793978239\ldots$ [Prove2MeSensitivity26]. The universal quartic upper bound remains.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{bs}(f)\). “\(\mathrm{bs}(f)\) in terms of it” is the pair with \(\mathrm{bs}(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 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\) | |
| AND total | \(n\) | |
| PARITY total | \(n\) | |
| MAJORITY total | \((n+1)/2\) | |
| Threshold total | \(\max\{k,\; n-k+1\}\) | |
| Symmetric functions (general) total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{bs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. |
| EXACT-HALF total | \(n\) | Sandwiched: $\mathrm{s}^1(f) \le \mathrm{bs}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| ODD-MAX-BIT total | \(\lfloor n/2 \rfloor + 1\) putative | Equal to $\mathrm{s}$, so blocks buy nothing. A sensitive block at $x$ either contains the current highest $1$ (at most one such block can be disjoint from the others) or has its own maximum above it, of parity opposite to $i$ -- and distinct disjoint blocks need distinct maxima. That caps the count at $1+\lceil (n-i)/2\rceil$, the same bound as for $\mathrm{s}$, and $x=e_1$ attains it. |
| ADDRESS / multiplexer total | \(k+1\) | |
| Binary tree navigation total | \(k\) | Squeezed between $\mathrm{s}=k$ and $\mathrm{C}=k$. |
| TRIBES total | \(\Theta(n/\log n)\) | |
| AND-OR tree (depth 2) total | \(n\) | |
| NAND tree (balanced AND-OR formula) total | \(\Theta(\sqrt{N})\) | |
| Recursive MAJORITY-of-3 total | \(2^d\) | |
| Kushilevitz's function (iterated) total | \(N\) | |
| Rubinstein's function total | \(n^2/2 = N/2\) | At $0^N$: the $n/2$ adjacent pairs inside each of the $n$ blocks are disjoint sensitive blocks. |
| Ambainis-Sun function total | \(6k^2+7k+2\) | Attained at the all-zero input: $\mathrm{bs}^0(f) = (3k+2)\cdot\mathrm{bs}^0(g) = (3k+2)(2k+1)$, since flipping the $j$-th pattern's two $1$-bits inside any block turns $f$ on, and blocks from different copies are disjoint. With $\mathrm{s} = 3k+2$ this is exactly $\tfrac23\mathrm{s}^2 - \tfrac13\mathrm{s}$, the current record constant for the quadratic separation. AmbainisSun11 |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{bs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| Meiburg's tournament-subcube function total | \(14011^{\,d}\) | The base case ($d=1$) is $\mathrm{bs} \ge 14011$, established -- and formally verified in Lean -- in [Meiburg26]. Block sensitivity is supermultiplicative under block composition (plant a $\mathrm{bs}$-maximising inner input in each copy and take unions of inner blocks across each outer block), so the $d$-fold composition has $\mathrm{bs} \ge 14011^{\,d}$. Exact, not merely a lower bound: $\mathrm{bs} \le \mathrm{C} = \mathrm{C}^0 = 14011^{\,d}$ by \(\mathrm{C}^0(f)\). Meiburg26 |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$. Upper $\mathrm{bs}\le\mathrm{C}$; lower $\mathrm{bs}\ge\mathrm{D}/\mathrm{C}=\widetilde\Omega(\sqrt n)$ from $\mathrm{D}\le\mathrm{C}\cdot\mathrm{bs}$. |
| Cheat-sheet functions total | \(\widetilde\Theta(\sqrt n)\) | Upgraded from the bare $\mathrm{bs}\le\mathrm{C}$ upper bound: $\mathrm{D}\le\mathrm{C}\cdot\mathrm{bs}$ with $\mathrm{C}=\widetilde O(\sqrt n)$ and $\mathrm{D}=\widetilde\Omega(n)$ forces $\mathrm{bs}=\widetilde\Omega(\sqrt n)$ as well. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n)\) putative | From $\mathrm{D}\le\mathrm{s}\cdot\mathrm{bs}^2$ with the recorded $\mathrm{s}=\widetilde O(n)$ and $\mathrm{D}=\widetilde\Omega(n^3)$: $\mathrm{bs}\ge\sqrt{\mathrm{D}/\mathrm{s}}=\widetilde\Omega(n)$. So the low-sensitivity function is not low-block-sensitivity: $\mathrm{bs}$ is already as large as $\mathrm{s}$. The available ceiling is $\mathrm{bs}\le 2\deg^2\le 2\mathrm{s}^4=\widetilde O(n^4)$ (Nisan-Szegedy composed with Huang's $\deg\le\mathrm{s}^2$); $\mathrm{bs}\le\mathrm{s}^2$ would give $\widetilde O(n^2)$ but is still conjectural. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{4/3})\) putative | From Nisan's $\mathrm{C}\le\mathrm{s}\cdot\mathrm{bs}$ [Nisan91] with $\mathrm{C}=\widetilde\Theta(n^2)$ and $\mathrm{s}=\widetilde\Theta(n^{2/3})$. No matching upper bound is available: that would need $\mathrm{bs}\le\mathrm{s}^2$, which is open -- [Huang19] gives only $\mathrm{bs}\le\mathrm{s}^4$. The ceiling here is the trivial $\mathrm{bs}\le\mathrm{C}=\widetilde O(n^2)$. If $\mathrm{bs}$ did sit at $\widetilde\Theta(n^{4/3})$ this family would also be an extremal $\mathrm{bs}=\widetilde\Theta(\mathrm{s}^2)$ example. |
| Gilmer-Saks-Srinivasan functions total | \(\Theta(n)\) | Squeezed between $\mathrm{bs}_0(f)=n\,\mathrm{bs}_0(g_n)\ge n$ and $\mathrm{fbs}=O(n)$. |
| Random-indicator gadget total | \(n\) | Squeeze: $\mathrm{s}\le\mathrm{bs}\le\mathrm{C}=n$. The whole gap between $\mathrm{C}^0$ and $\mathrm{bs}^0$ is invisible to the two-sided measures, which the $1$-side saturates. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Theta(\sqrt n)\) putative | Lower $\mathrm{bs}\ge\mathrm{s}$. Upper: $\mathrm{bs}_1\le\mathrm{C}_1=\widetilde O(\sqrt n)$, and disjoint sensitive blocks at a $0$-input inject into the $k$ columns (two disjoint blocks cannot both complete the same column), so $\mathrm{bs}_0=O(k)$. Against $\mathrm{C}=\widetilde\Theta(n)$ this makes the function an extremal example for $\mathrm{C}=O(\mathrm{bs}^2)$ as well, alongside \(f_{\mathrm{GSS}}\). |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Theta(n^{1/3})\) putative | Lower $\mathrm{bs}\ge\mathrm{s}$. Upper: $\mathrm{bs}_1\le\mathrm{C}_1$, and disjoint sensitive blocks at a $0$-input inject into the $k$ columns. Together with $\mathrm{C}=\widetilde\Theta(n^{2/3})$ this makes $\mathrm{C}=\widetilde\Theta(\mathrm{s}\cdot\mathrm{bs})$, i.e. Nisan's bound is tight on this family. |
| Ambainis' exact-quantum function total | \(3^d\) | Squeeze: $\mathrm{s}\le\mathrm{bs}\le n$. |
| FORRELATION partial | \(O(1)\) | Two arguments, the second much sharper. Counting: flipping $m$ coordinates moves $\Phi$ by at most $2m/\sqrt n$, so every sensitive block has $\Omega(\sqrt n)$ coordinates and at most $O(\sqrt n)$ of them are disjoint. Adversary: $\mathrm{bs}(f) \le \mathrm{Adv}(f)^2$ holds for partial $f$ as well (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\) -- disjointness of the blocks is all the proof uses), and $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$ here. So block sensitivity is constant against $\mathrm{D} = \Theta(n)$, and it does not even see the $\widetilde\Theta(\sqrt n)$ scale of $\mathrm{R}$. |
| k-FORRELATION partial | \(O(k^2)\) | $\mathrm{bs} \le \mathrm{Adv}^2$ for partial $f$ (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\)), and $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(k)$. Also $\mathrm{bs} \le \mathrm{fbs}$. |
| Simon's problem partial | \(2\) putative | Every sensitive block has size $\ge 2^{n-1}$: crossing between the injective and the two-to-one side requires touching each of the $2^{n-1}$ pairs $\{x, x\oplus s\}$ at least once. Two disjoint blocks of exactly that size exist -- the two transversals of the pairing -- and three do not fit in $2^n$ points. So $\mathrm{bs}^0 = \mathrm{bs}^1 = 2$. |
| Deutsch-Jozsa partial | \(2\) putative | At $0^N$ the sensitive blocks are exactly the $\binom{N}{N/2}$ half-sized sets, and two disjoint halves fit; at a balanced $x$ they are exactly $\mathrm{supp}(x)$ and its complement, again two disjoint blocks. Three disjoint blocks of size $N/2$ do not fit in $N$ coordinates, so $\mathrm{bs}^0=\mathrm{bs}^1=2$. |
| Bernstein-Vazirani partial | \(1\) putative | The sensitive blocks at the input $x$ indexed by $s$ are exactly the sets $B_d = \{i : \langle d, i\rangle = 1\}$ for $d = s \oplus s' \ne 0$. Any two of them meet -- $|B_{d} \cap B_{d'}| = 2^{n-2} > 0$ for distinct nonzero $d, d'$ -- so no two disjoint sensitive blocks exist. Hence $\mathrm{s} = 0 < \mathrm{bs} = 1$, itself a small curiosity that no total function allows. |
| Unique search partial | \(n\) | |
| Two-or-none search partial | \(\lfloor n/2 \rfloor\) putative | The maximum of $\mathrm{bs}^0 = \lfloor n/2\rfloor$ and $\mathrm{bs}^1 = 1$. |
| Marked bit partial | \(1\) putative | An answer-flipping block must clear every current mark and plant one of the other colour, so all sensitive blocks contain the encoding bit of some fixed existing mark and no two are disjoint. There is at least one, so $\mathrm{bs} = 1$. |
| Dense marked bit partial | \(1\) putative | At any $x$ every sensitive block must clear all of $x$'s marks and plant $n/2$ of the other colour, so all sensitive blocks at $x$ share the coordinates of $x$'s marks and no two are disjoint. |
| Gap-Majority partial | \(\Theta(\min(n, 1/\delta))\) | Every sensitive block at a promise input must move at least $2\delta n$ coordinates, so disjoint blocks number at most $1/(2\delta)$; and at an input of weight exactly $n/2+\delta n$ that many disjoint blocks of $2\delta n$ ones each do flip the answer. |
| Gap-Majority at constant gap partial | \(1\) | A sensitive block must move at least $2\delta n = n/2$ coordinates, and an input of weight $3n/4$ has room for exactly one such block. |
| Parity-labelled FIND-1 partial | \(1\) putative | Exactly $1$. A sensitive block at $x$ must produce a domain input of the other value, and such an input is $0$ on all of $\mathrm{supp}(x)$; so every sensitive block contains $\mathrm{supp}(x)$ and no two of them are disjoint. One block exists -- swap $\mathrm{supp}(x)$ for any $n/4$ coordinates of the other parity -- so $\mathrm{bs} = 1$ while $\mathrm{D} = n/4+1$. |
| Approximate index partial | \(1\) putative | Exactly one, so no two sensitive blocks are disjoint. After any answer-flipping change every non-$2$ cell holds $1-v$, whereas at present every one of the $|B(a,r)|$ cells of the ball holds $v$; so every sensitive block contains the whole ball, and any two of them meet. There is at least one (rewrite everything), so $\mathrm{bs} = 1$. |
| Collision problem partial | \(2\) putative | Crossing between the two sides forces a change in each of the $n/2$ pairs, so every sensitive block has $\ge n/2$ of the $n$ coordinates: at most two disjoint ones, and two transversals of the pairing achieve it. $\mathrm{bs}^0 = \mathrm{bs}^1 = 2$. |
| Element distinctness total | \(n\) putative | The $n$ singleton blocks above are disjoint, and $\mathrm{bs} \le n$. |
| Ambainis-Belovs function partial | \(O(1)\) | $\mathrm{bs} \le \mathrm{Adv}^2 = O(1)$ -- a chain that holds for partial functions, because each $x^{B_j}$ in Ambainis' argument is a domain point by definition of a sensitive block. So block sensitivity is blind to the $\Omega(n^{1/3})$ lower bound, as is everything below it. Ambainis02 |
| Surjectivity total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{bs}(f) \le n$, with $\mathrm{s} = \Theta(n)$ here. |
| $k$-distinctness total | \(\Theta(n)\) | $\mathrm{s} \le \mathrm{bs} \le n$. |
| Triangle finding total | \(\Theta(m^2) = \Theta(n)\) | Sandwiched: $\mathrm{s} \le \mathrm{bs} \le \mathrm{C} \le \binom m2$. |
| Recursive Fourier sampling partial | \(1\) putative | The promise is rigid enough that no block of the oracle can be flipped and stay inside it. Worth recording because it is precisely why the polynomial method says nothing here. Aaronson10 |
| Ordered search partial | \(2\) putative | Decision version. Flipping a block $B$ of $0^k1^{n-k}$ stays on the promise only if $B$ is the interval between the old and the new boundary, so every sensitive block contains position $k$ (if it moves the boundary down) or position $k+1$ (if it moves it up). Two disjoint sensitive blocks are therefore the most possible, and $k\pm1$ supplies them. |
| Inner product mod 2 total | \(n\) | Pinned: $\mathrm{s} \le \mathrm{bs} \le \mathrm{D}$ and both ends are $n$. The same sandwich fixes $\mathrm{fbs}$, $\mathrm{C}$, $\mathrm{RC}$, $\mathrm{UC}$ and $\mathrm{Dna}$ at $n$. |
| Minsky-Papert one-in-a-box total | \(m^2 = N^{2/3}\) | From $\mathrm{bs}^0$. Together with $\mathrm{D} = N = m^3$ this is a cube-root gap, the largest a read-once formula allows. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Take a tournament in which $k$ vertices have out-degree exactly $1$; each such vertex is one edge-flip from being a sink, and the flips are distinct edges, so $\mathrm{bs} \ge k$. Counting out-degrees, $k + (m-k)(m-1) \ge \binom m2$ allows $k = \Theta(m)$. Upper: $\mathrm{bs} \le \mathrm{D} = O(m)$. |
| Scorpion graphs total | \(\Theta(m)\) | Squeezed between $\mathrm{s} = 3m-6$ and $\mathrm{C} = \Theta(m)$. |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) | From $\mathrm{bs}^0$. |
| OpenAI’s nested tournament sensitivity separator total | \(\Omega(36122005036315302778151792217492267728323576313688938488653910762565727724823376796778788409135057260835654187889331715677969332701578439948333928007781625724245588074795233962798724758384452483^m)\) | Corollary 4.3: block sensitivity at zero ≥B^m, B=M²(2M²+1)⁹. OpenAISensitivity26 |
| AND of complemented EXACT-ONE functions total | \(m^2\) | All m² bits are sensitive at zero; the arity is the matching ceiling. KLLPV26 |