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

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.

Other measure \(\mathrm{bs}(f)\) in terms of it It in terms of \(\mathrm{bs}(f)\)
\(\mathrm{s}(f)\) Sensitivity total2.1308,4 partial∞ open pair → total1,1 partial1,1 open pair →
\(\mathrm{fbs}(f)\) Fractional block sensitivity total1,1 partial1,1 open pair → total1.5,2 partial1.5,? open pair →
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 open pair → total2,2 partial∞ open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 open pair → total2,3 partial∞ open pair →
\(\mathrm{RC}(f)\) Randomized certificate complexity total1,1 partial1,1 open pair → total1.5,2 partial1.5,? open pair →
\(\mathrm{bs}^0(f)\) 0-block sensitivity total∞ partial∞ open pair → total1,1 partial1,1 open pair →

The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.

Known values

FunctionValueNotes
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