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

1-block sensitivity

Block sensitivity maximised only over 1-inputs.

Definition

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

Basic facts

  • $\mathrm{bs}(f) = \max(\mathrm{bs}^0(f), \mathrm{bs}^1(f))$ and $\mathrm{s}^1(f) \le \mathrm{bs}^1(f)$.
  • $\mathrm{C}^1(f) \le \mathrm{s}^0(f)\,\mathrm{bs}^1(f)$ [Nisan91], the one-sided form of $\mathrm{C} \le \mathrm{s}\cdot\mathrm{bs}$.
  • $\mathrm{bs}^1(f) = \mathrm{bs}^0(\bar f)$, so every statement about one is a statement about the other with $f$ negated.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{bs}^1(f)\). “\(\mathrm{bs}^1(f)\) in terms of it” is the pair with \(\mathrm{bs}^1(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}^1(f)\) in terms of it It in terms of \(\mathrm{bs}^1(f)\)
\(\mathrm{bs}(f)\) Block sensitivity total1,1 partial1,1 open pair → total∞ partial∞ open pair →
\(\mathrm{bs}^0(f)\) 0-block sensitivity total∞ partial∞ derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{s}^1(f)\) 1-sensitivity total1,? partial1,? derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{C}^1(f)\) 1-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 \(1\)
AND total \(n\)
PARITY total \(n\)
MAJORITY total \((n+1)/2\)
Threshold total \(k\)
EXACT-HALF total \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{bs}^1(f) \le \mathrm{D}(f)$, with both ends $n$ here.
ODD-MAX-BIT total \(\lfloor n/2 \rfloor + 1\) putative Equal to $\mathrm{s}^1$, and to $\mathrm{bs}$.
ADDRESS / multiplexer total \(k+1\) Squeezed between $\mathrm{s}^1 = k+1$ and $\mathrm{bs} = k+1$.
Binary tree navigation total \(k\) Squeezed between $\mathrm{s}^1 = k$ and $\mathrm{C}^1 = k$.
TRIBES total \(\Theta(\log n)\) At most $\mathrm{C}^1 = w$, and the $w$ singletons inside the satisfied tribe achieve it.
AND-OR tree (depth 2) total \(n\)
NAND tree (balanced AND-OR formula) total \(2^{\lfloor d/2\rfloor} = \Theta(\sqrt N)\) putative As \(\mathrm{bs}^0(f)\), with the sides exchanged.
Recursive MAJORITY-of-3 total \(2^d\) Between $\mathrm{s}^1 = 2^d$ and $\mathrm{bs} = 2^d$.
Kushilevitz's function (iterated) total \(N\) Between $\mathrm{s}^1 = N$ and the trivial ceiling $N$.
Rubinstein's function total \(n = \sqrt N\) putative Every sensitive block of a $1$-input must stop the firing block, so all of them meet its $n$ bits and at most $n$ are disjoint; the $n$ singletons work. So the quadratic gap is entirely one-sided: $\mathrm{bs}^0 = \tfrac12(\mathrm{bs}^1)^2$.
Ambainis-Sun function total \(3k+2\) putative Every sensitive block of a $1$-input must destroy the pattern that is firing, so it meets that pattern's $3k+2$ pinned bits; at most $3k+2$ such blocks are disjoint, and the singletons work. So the separation is one-sided, as in \(f_{\mathrm{Rub}}\).
AND composed with NOT-EXACT-HALF total \(n^2/2 + n\) putative Equal to $\mathrm{s}^1$: a sensitive block must push some block from weight $n/2+t$ to $n/2$, hence contains at least $t$ of that block's ones, so a block at distance $t$ supports at most $(n/2+t)/t$ disjoint sensitive blocks -- maximised at $t=1$, giving $n/2+1$ per block and $n(n/2+1)$ in all.
Pointer functions total \(\widetilde\Theta(\sqrt n)\) putative Variant $f_{2m,m}$. The $2m$ singleton blocks of the $\mathrm{s}^1$ line are pairwise disjoint and each is sensitive, so $\mathrm{bs}^1\ge\mathrm{s}^1=\widetilde\Omega(\sqrt n)$; the ceiling is $\mathrm{bs}^1\le\mathrm{bs}=\widetilde O(\sqrt n)$.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{bs}^1\le\mathrm{bs}=\widetilde O(\sqrt n)$. Nisan's refined bound $\mathrm{C}^1\le\mathrm{s}^0\,\mathrm{bs}^1$ with $\mathrm{C}^1=\widetilde\Theta(\sqrt n)$ and $\mathrm{s}^0=\widetilde O(\sqrt n)$ gives only $\mathrm{bs}^1=\widetilde\Omega(1)$, so neither side of $\mathrm{bs}$ can be pinned from the recorded data.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n)\) Squeeze: $\mathrm{bs}_1\le\mathrm{C}^1\le\mathrm{UC}_1=\widetilde O(n)$. Read against the recorded $\mathrm{bs}_0=\widetilde\Omega(n^{4/3})$ this makes the block sensitivity of this family genuinely one-sided: all of it lives on the $0$-inputs, exactly like $\mathrm{C}$.
Gilmer-Saks-Srinivasan functions total \(n\) putative Squeezed between $\mathrm{s}_1=n$ and $\mathrm{C}^1=n$. So the whole $\mathrm{C}$-vs-$\mathrm{bs}$ gap of this family lives on the $0$-side, where $\mathrm{C}^0=\Theta(n^2)$ but $\mathrm{bs}_0=\Theta(n)$.
Random-indicator gadget total \(n\) putative Squeeze: $\mathrm{s}^1\le\mathrm{bs}^1\le\mathrm{C}^1$, both $n$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(\sqrt n)\) putative Squeezed between $\mathrm{s}_1=\widetilde\Omega(\sqrt n)$ and $\mathrm{C}^1=\widetilde O(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{1/3})\) putative Squeezed between $\mathrm{s}_1=\widetilde\Omega(n^{1/3})$ and $\mathrm{C}^1=\widetilde O(n^{1/3})$.
Ambainis' exact-quantum function total \(\Theta(3^d)\) putative Lower: at the $1$-input above (child $1$ all-zero, children $2,3$ equal to $1$) each single bit of child $1$ is a sensitive block, giving $\mathrm{bs}_1\ge 3^{d-1}$. Upper: $\mathrm{bs}_1\le\mathrm{C}^1=(3^d+1)/2$. Unlike sensitivity, block sensitivity is maximal on both sides.
FORRELATION partial \(O(1)\) See $\mathrm{bs}$: $\mathrm{bs}^1 \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 a balanced $x$ the sensitive blocks are exactly $\mathrm{supp}(x)$ and its complement.
Bernstein-Vazirani partial \(1\) See $\mathrm{bs}^0$.
Unique search partial \(1\) From $e_i$ the only block whose flip stays in the domain and changes the value is $\{i\}$; flipping $\{i,j\}$ gives $e_j$, another $1$-input.
Two-or-none search partial \(1\) putative From $e_i + e_j$ the only block whose flip both stays on the promise and changes the value is $\{i,j\}$ itself; flipping one of the two, or a pair of zeros, leaves the domain, and flipping $\{i,k\}$ gives another $1$-input.
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 See $\mathrm{bs}^0$.
Gap-Majority at constant gap partial \(1\) putative See $\mathrm{bs}^0$.
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 \(n\) putative The $n$ singleton blocks at an all-distinct input.
Ambainis-Belovs function partial \(O(1)\) At most $\mathrm{bs} = O(1)$.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{bs}^1(f) \le n$, with $\mathrm{s}^1 = \Theta(n)$ here. (At $R=4$, $N=8$ the exhaustive value is $\mathrm{bs}^1 = 8 = n/2 = \mathrm{C}^1$.)
$k$-distinctness total \(k\) putative Disjoint sensitive blocks at a $1$-input must each meet every $k$-group, and a $k$-group has only $k$ positions, so $\mathrm{bs}^1 \le k$; the single-$k$-group input attains it.
Triangle finding total \(3\) putative Same argument as $\mathrm{s}^1$: every sensitive block must delete an edge of every triangle, so disjoint blocks inject into the $3$ edges of any one triangle.
Recursive Fourier sampling partial \(1\) putative Same construction as $\mathrm{bs}^0$, run from a $1$-input.
Ordered search partial \(2\) putative Same argument as $\mathrm{bs}$, at an interior $k$ of odd parity.
Inner product mod 2 total \(\Theta(n)\) Between $\mathrm{s}^1 = \Theta(n)$ and $\mathrm{bs} = n$.
Minsky-Papert one-in-a-box total \(m\) At a $1$-input with exactly one $1$ per box, the $m$ singleton blocks are minimal and disjoint.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Between $\mathrm{s}^1 = m-1$ and $\mathrm{bs} = O(m)$.
Scorpion graphs total \(3m-6\) putative Squeezed between $\mathrm{s}^1$ and $\mathrm{C}^1$, both $3m-6$.
Graph connectivity total \(m-1\) putative Squeezed between $\mathrm{s}^1 = m-1$ and $\mathrm{C}^1 = m-1$.