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