Q The Query Complexity Zoo
\(\mathrm{cbs}(S)\)

Critical block sensitivity

Block sensitivity of a search problem: the adversary picks the input, but the algorithm picks which valid answer to commit to.

Definition

Defined for a search problem $S \subseteq \{0,1\}^n \times \mathcal{O}$. Call an input $x$ critical if it has exactly one valid answer, $|S(x)| = 1$. A solution function is any $s : \{0,1\}^n \to \mathcal{O}$ with $(x, s(x)) \in S$ for all $x$; for such an $s$, $\mathrm{bs}(s,x)$ is the ordinary block sensitivity of $s$ at $x$ (blocks whose flip changes the value of $s$, which is now not necessarily Boolean). Then $$\mathrm{cbs}(S) \ =\ \min_{s} \ \max_{x \text{ critical}} \ \mathrm{bs}(s,x).$$ The minimum over $s$ is what makes this a measure of the problem rather than of a particular algorithm: a search problem is only hard if every way of committing to answers is sensitive somewhere on a critical input.

Basic facts

  • $\mathrm{cbs}(f) = \mathrm{bs}(f)$ for Boolean $f$; the measure only says something new when an input has several valid answers.
  • Lifting: $\mathrm{R}^{cc}(S \circ g^n) = \Omega(\mathrm{cbs}(S))$ for a suitable constant-size gadget $g$ [GoosPitassi14]. This is the source of the tight monotone-circuit-depth and Cutting-Planes lower bounds obtained there.
  • For the false-clause search problem of a random $\Delta$-dense unsatisfiable $k$-CNF, $\mathrm{cbs} = \Omega(n)$; for the Tseitin search problem on a bounded-degree expander, $\mathrm{cbs} = \Omega(n)$ [GoosPitassi14].
  • The min over solution functions is essential: the maximum over $s$ can be large for trivially easy search problems.
  • The max over critical inputs is equally essential, and it cuts the other way: a search problem in which every input has at least two valid answers has no critical inputs at all, so the max is over the empty set and $\mathrm{cbs} = 0$. \(\mathrm{Find1}_{\ge n/2}\), \(\mathrm{ApproxHW}\) and \(\mathrm{AGREE}_n\) are of this kind, and there $\mathrm{cbs}$ certifies nothing whatsoever -- not a weak bound but no bound, so the relational column reads $\infty$ against it.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{cbs}(S)\). “\(\mathrm{cbs}(S)\) in terms of it” is the pair with \(\mathrm{cbs}(S)\) 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{cbs}(S)\) in terms of it It in terms of \(\mathrm{cbs}(S)\)
\(\mathrm{bs}(f)\) Block sensitivity total1,1 partial1,1 open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{RS}(f)\) Sabotage complexity total1,2 partial1,2 derived open pair → total2,3 partial2,? derived open pair →
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity total1,1 partial1,1 relation1,1 derived open pair → total2,3 partial∞ relation∞ derived open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 relation1,1 derived open pair → total2,3 partial∞ relation∞ 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\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, attained at $0^n$. The measure only says something new for search problems where some input has several valid answers. GoosPitassi14
AND total \(n\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, attained at $1^n$. GoosPitassi14
PARITY total \(n\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$: every one of the $n$ coordinates is sensitive at every input. GoosPitassi14
MAJORITY total \((n+1)/2\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $(n+1)/2$ at a balanced input. GoosPitassi14
Threshold total \(\max\{k,\; n-k+1\}\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, recorded on the \(\mathrm{bs}(f)\) line. GoosPitassi14
Symmetric functions (general) total \(\Theta(n)\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, and $\mathrm{bs}(f) = \Theta(n)$ for every non-constant symmetric $f$ by the \(\mathrm{bs}(f)\) line. GoosPitassi14
EXACT-HALF total \(n\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $n$ here, attained at any input of weight $n/2$. GoosPitassi14
ODD-MAX-BIT total \(\lfloor n/2 \rfloor + 1\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, recorded on the \(\mathrm{bs}(f)\) line. GoosPitassi14
ADDRESS / multiplexer total \(k+1\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $k+1$ here by the \(\mathrm{bs}(f)\) line. GoosPitassi14
Binary tree navigation total \(k\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $k$ here by the \(\mathrm{bs}(f)\) line. GoosPitassi14
TRIBES total \(\Theta(n/\log n)\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $\Theta(n/\log n)$ here by the \(\mathrm{bs}(f)\) line. GoosPitassi14
AND-OR tree (depth 2) total \(n\) Critical block sensitivity coincides with ordinary block sensitivity on a Boolean-valued problem [GoosPitassi14]: the only solution function is $f$ itself and every input is critical, so $\mathrm{cbs} = \mathrm{bs} = n$. GoosPitassi14
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt N)\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14] -- every input is critical and $f$ is the only solution function -- and $\mathrm{bs} = \Theta(\sqrt N)$. GoosPitassi14
Recursive MAJORITY-of-3 total \(2^d\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14], and $\mathrm{bs} = 2^d$. GoosPitassi14
Kushilevitz's function (iterated) total \(N\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14], and $\mathrm{bs} = N$: the function is fully block sensitive. GoosPitassi14
Rubinstein's function total \(N/2 = n^2/2\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14]; the recorded $\mathrm{bs} = n^2/2$ is attained at the all-zeros input, whose $n^2/2$ sensitive blocks are the consecutive pairs. GoosPitassi14
Ambainis-Sun function total \(6k^2+7k+2\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14], and $\mathrm{bs} = \mathrm{bs}^0 = 6k^2+7k+2$ is attained at the all-zeros input. GoosPitassi14
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14], and $\mathrm{bs} = \Theta(n^2)$. GoosPitassi14
Meiburg's tournament-subcube function total \(14011^{\,d}\) putative $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14]. Here $\mathrm{bs}$ is in fact pinned exactly rather than merely bounded below: $14011^{\,d} \le \mathrm{bs}^0 \le \mathrm{bs} \le \mathrm{C} \le 14011^{\,d}$, using \(\mathrm{bs}^0(f)\) and \(\mathrm{C}^0(f)\). GoosPitassi14 Meiburg26
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $f_{2m,m}$: for a Boolean function the solution function is forced and every input is critical, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}=\widetilde\Theta(\sqrt n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
Cheat-sheet functions total \(\widetilde\Theta(\sqrt n)\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}=\widetilde\Theta(\sqrt n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n)\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\widetilde\Omega(n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3})\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\widetilde\Omega(n^{4/3})$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\Theta(n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(\sqrt n)\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\widetilde\Theta(\sqrt n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{1/3})\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\widetilde\Theta(n^{1/3})$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
Ambainis' exact-quantum function total \(3^d\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=3^d$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
FORRELATION partial \(O(1)\) Degenerate on a Boolean function: every input is critical and the solution function is forced, so $\mathrm{cbs} = \mathrm{bs} = O(1)$. GoosPitassi14
k-FORRELATION partial \(O(k^2)\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = O(k^2)$. GoosPitassi14
Simon's problem partial \(2\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. GoosPitassi14
Deutsch-Jozsa partial \(2\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. In particular the measure that governs $\mathrm{Search}(\varphi)$ says nothing here. GoosPitassi14
Bernstein-Vazirani partial \(1\) Degenerate: every input is critical (one valid output), so the solution function is forced and $\mathrm{cbs} = \mathrm{bs} = 1$. GoosPitassi14
Marked bit partial \(1\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 1$. GoosPitassi14
Dense marked bit partial \(1\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 1$. GoosPitassi14
Unstructured search (relation) relation \(n\) putative Exactly $n$, and for every solution function -- so the min over solution functions in the definition of \(\mathrm{cbs}(S)\) does nothing here. The all-zero input is critical: its only valid answer is $\bot$. Flipping any single coordinate $i$ turns it into $e_i$, whose only valid answer is $i \ne \bot$, so all $n$ singletons are sensitive blocks at $0^n$ whatever $s$ is; and $\mathrm{cbs} \le \mathrm{D} = n$. Compare $\mathrm{Q} = \Theta(\sqrt n)$: critical block sensitivity is a classical measure and sees none of the Grover speed-up.
FIND-1 under a density promise relation \(0\) putative Vacuously: \(\mathrm{cbs}(S)\) maximises over critical inputs, those with a unique valid answer, and this problem has none. A promise input has $|x| \ge n/2 \ge 2$ ones for $n \ge 4$, so every input admits at least two answers and the max is over the empty set. So critical block sensitivity -- the standard route to relational lower bounds -- says nothing whatever about a problem with $\mathrm{D} = n/2+1$. Contrast \(\mathrm{Search}(\varphi)\) and \(\mathrm{SEARCH}_n\), where the unique-answer inputs are exactly what carries the hardness.
Approximate Hamming weight relation \(0\) putative Vacuously: an input is critical for \(\mathrm{cbs}(S)\) when it has a unique valid answer, and here the valid answers at $x$ are all integers in $[\,|x|-\varepsilon n,\ |x|+\varepsilon n\,]$, an interval containing $\ge 2\varepsilon n \ge 2$ of them. So there are no critical inputs and the maximum in the definition is empty. Critical block sensitivity is blind to approximate-counting hardness, which is why the $\mathrm{psD}$ lower bound of [CDM23] needs a different technique.
Correlated-string search relation \(0\) putative No input has a unique valid answer -- there are $\binom{n}{\le n/2-\sqrt n}$ of them -- so there are no critical inputs and the maximum in the definition of \(\mathrm{cbs}(S)\) is empty. As at \(\mathrm{ApproxHW}\), the standard route to relational lower bounds is unavailable and [GLSS19] had to argue directly.
SearchCNF relation \(\Theta(1)\) putative For the random $\Delta$-dense formula this entry is otherwise about -- not $\Theta(n)$. Critical block sensitivity lower-bounds the randomized cost: let $s$ be the plurality output of a bounded-error algorithm, take a critical $x$ and $b$ disjoint blocks with $s(x^B) \ne s(x)$; an algorithm that never queries inside $B$ cannot answer whp at both $x$ and $x^B$, so it must enter each block with constant probability and $\mathrm{cbs} = O(\mathrm{R})$. Here $\mathrm{R} = \Theta(1)$. [ABK21lifting] give the same conclusion through $\mathrm{cbs} = O(\mathrm{CA})$ with $\mathrm{CA} = \Theta(1)$. The famous $\mathrm{cbs} = \Theta(n)$ belongs to the Tseitin contradiction on a bounded-degree expander [HuynhNordstrom12, GoosPitassi14], where an assignment can falsify a single vertex constraint and random sampling therefore fails -- see \(\mathrm{Ts}(G)\). Against $\mathrm{D} = \Theta(n)$ this makes the dense random formula an unbounded $\mathrm{D}$-vs-$\mathrm{cbs}$ separation rather than the $\Theta(1)$ ratio previously recorded. GoosPitassi14 HuynhNordstrom12 ABK21lifting
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = \Theta(\min(n,1/\delta))$. GoosPitassi14
Gap-Majority at constant gap partial \(\Theta(1)\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs}$. GoosPitassi14
Approximate index partial \(1\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 1$. GoosPitassi14
Collision problem partial \(2\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. GoosPitassi14
Element distinctness total \(n\) Degenerate on a Boolean-valued function: every input is critical and the solution function is forced, so $\mathrm{cbs} = \mathrm{bs} = n$. GoosPitassi14
Ambainis-Belovs function partial \(O(1)\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = O(1)$. So the measure is as blind to this function as block sensitivity is. GoosPitassi14
Welded trees relation \(\Theta(1)\) putative Contrast \(\mathrm{Ts}(G)\), where $\mathrm{cbs} = \Theta(n)$. Every input is critical -- the valid answer $\pi(\mathrm{EXIT})$ is unique -- so the solution function $s$ is forced and $\mathrm{cbs} = \max_x \mathrm{bs}(s,x)$. Let $B$ be a block whose flip changes the answer, and put $y = \pi(\mathrm{EXIT})$. In the modified instance $y$ is not the exit, so $y$ is either a degree-$3$ vertex or not a vertex at all; either way one of the nine cells $(y,c)$ has changed, so $B$ meets $\{(y,c)\}_{c=1}^{9}$. Disjoint blocks therefore number at most nine. At least one exists (rename the exit), so $\mathrm{cbs} = \Theta(1)$ -- which is the witness behind the recorded fact that $\mathrm{D}$ is unbounded in terms of $\mathrm{cbs}$ (\(\mathrm{D}(f)\) vs \(\mathrm{cbs}(S)\)).
Tseitin search on an expander relation \(\Theta(n)\) The theorem the measure exists for. Expansion is what forces it: any solution function must commit to a violated vertex, and flipping the edges along a path to a far-away vertex moves the violation, so no commitment is stable. Contrast \(\mathrm{Search}(\varphi)\) on a random dense formula, where a constant fraction of clauses is falsified, $\mathrm{R} = \Theta(1)$, and therefore $\mathrm{cbs} = \Theta(1)$ as well. HuynhNordstrom12 GoosPitassi14
Inner product mod 2 total \(n\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)); here $\mathrm{bs} = n$.
Minsky-Papert one-in-a-box total \(m^2 = N^{2/3}\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)); here $\mathrm{bs} = m^2$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
Scorpion graphs total \(\Theta(m)\) For a Boolean function the solution to be produced is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)); here $\mathrm{bs} = \Theta(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) For a Boolean function the solution to be produced is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)); here $\mathrm{bs} = \Theta(m^2)$.