Fractional block sensitivity
LP relaxation of block sensitivity; equals the LP relaxation of certificate complexity by duality.
also written:
fractional certificate complexity (LP dual), FC(f)
Definition
$\mathrm{fbs}_x(f)$ is the optimum of the LP $$\max \sum_{B} w_B \quad \text{s.t.}\quad \sum_{B \ni i} w_B \le 1\ \forall i,\quad w_B \ge 0,$$ where $B$ ranges over sensitive blocks of $x$. Its LP dual is the fractional certificate complexity $\mathrm{FC}_x(f)$ (a fractional vertex cover of the blocks), so $\mathrm{fbs} = \mathrm{FC}$ exactly.
Basic facts
- $\mathrm{bs}(f) \le \mathrm{fbs}(f) \le \mathrm{C}(f)$.
- $\mathrm{fbs}(f) \le \mathrm{bs}(f)^{?}$ -- the best known separation is $\mathrm{fbs} = \Omega(\mathrm{bs}^{3/2})$ and the best upper bound is $\mathrm{fbs} = O(\mathrm{bs}^2)$ [GSS16].
- $\mathrm{fbs}(f) = O(\widetilde{\deg}(f)^2)$ [Kulkarni-Tal].
Equivalent / near-equivalent measures
- \(\mathrm{RC}(f)\) $\mathrm{fbs}(f) = \Theta(\mathrm{RC}(f))$ KulkarniTal16 Aaronson08
- \(\mathrm{CA}(f)\) $\mathrm{fbs}(f) = \Theta(\mathrm{CA}(f))$ for total $f$ ABIKPS17
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{fbs}(f)\). “\(\mathrm{fbs}(f)\) in terms of it” is the pair with \(\mathrm{fbs}(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\) | Squeezed: $\mathrm{bs}\le\mathrm{fbs}\le\mathrm{C}$ and both ends are $(n+1)/2$. The certificate LP is integral for MAJ. Aaronson08 |
| Threshold total | \(\max\{k,\;n-k+1\}\) | Between $\mathrm{bs}$ and $\mathrm{C}$, which coincide here. |
| Symmetric functions (general) total | \(\Theta(n)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. |
| EXACT-HALF total | \(n\) | Sandwiched: $\mathrm{s}^1(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| ODD-MAX-BIT total | \(\lfloor n/2 \rfloor + 1\) putative | The same argument survives the fractional relaxation: charge each block to its maximum index, and the load constraint at that coordinate caps the total weight per admissible maximum at $1$. |
| ADDRESS / multiplexer total | \(k+1\) | Between $\mathrm{bs}=k+1$ and $\mathrm{C}=k+1$. |
| Binary tree navigation total | \(k\) | Squeezed between $\mathrm{bs}=k$ and $\mathrm{C}=k$. |
| TRIBES total | \(\Theta(n/\log n)\) | Between $\mathrm{bs}$ and $\mathrm{C}$, which agree up to constants. |
| AND-OR tree (depth 2) total | \(n\) | |
| NAND tree (balanced AND-OR formula) total | \(\Theta(\sqrt N)\) | Between $\mathrm{bs}$ and $\mathrm{C}$, which agree here. |
| Recursive MAJORITY-of-3 total | \(2^d\) | Between $\mathrm{bs}=2^d$ and $\mathrm{C}=2^d$. |
| Kushilevitz's function (iterated) total | \(N\) | |
| Rubinstein's function total | \(\Theta(N)\) | Between $\mathrm{bs}=N/2$ and $\mathrm{C}=\Theta(N)$. |
| Ambainis-Sun function total | \(6k^2+7k+2\) | Pinned between $\mathrm{bs}$ and $\mathrm{C}$, which coincide at $(3k+2)(2k+1)$ here. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| Meiburg's tournament-subcube function total | \(14011^{\,d}\) putative | Squeezed exactly between $\mathrm{bs} = 14011^{\,d}$ and $\mathrm{C} = 14011^{\,d}$. |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) | Squeezed between $\mathrm{bs}$ and $\mathrm{C}$, which coincide here. |
| Cheat-sheet functions total | \(\widetilde\Theta(\sqrt n)\) | Squeezed between $\mathrm{bs}$ and $\mathrm{C}$, which coincide here. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{fbs}\ge\mathrm{bs}$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{4/3})\) | Squeeze: $\mathrm{fbs}\ge\mathrm{bs}$. The ceiling is $\mathrm{fbs}\le\mathrm{C}=\widetilde O(n^2)$. |
| Gilmer-Saks-Srinivasan functions total | \(\Theta(n)\) | Upper: $\mathrm{fbs}(f)\le\max\{n\,\mathrm{fbs}_0(g_n),\mathrm{fbs}_1(g_n)\}=O(n)$, since the pairwise-distance property caps $\mathrm{fbs}_0(g_n)$ at $200$ [GSS16, Thm 32]. Lower: $\mathrm{fbs}\ge\mathrm{bs}\ge\mathrm{bs}_0(f)=n\,\mathrm{bs}_0(g_n)\ge n$. GSS16 |
| Random-indicator gadget total | \(n\) | Squeeze: $\mathrm{bs}\le\mathrm{fbs}\le\mathrm{C}=n$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(\sqrt n)\) | From $\mathrm{C}=O(\mathrm{fbs}^2)$ [Tal13] against $\mathrm{C}=\widetilde\Theta(n)$. The block-injection argument recorded under $\mathrm{bs}$ suggests the matching $\widetilde O(\sqrt n)$, but the fractional relaxation is not covered by it. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/3})\) | From $\mathrm{C}=O(\mathrm{fbs}^2)$ [Tal13] against $\mathrm{C}=\widetilde\Theta(n^{2/3})$. |
| Ambainis' exact-quantum function total | \(3^d\) | Squeeze: $\mathrm{bs}\le\mathrm{fbs}\le n$. |
| FORRELATION partial | \(O(1)\) | The fractional relaxation is constant too, by the quantum certificate route rather than by counting: $\mathrm{fbs}(f) = \Theta(\mathrm{RC}(f)) = \Theta(\mathrm{QC}(f)^2)$ for partial $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{QC} \le \mathrm{Q} = 1$ since an algorithm computing $f$ also verifies its input. The load count of the $\mathrm{bs}$ entry only gives $O(\sqrt n)$; this is the right answer. |
| k-FORRELATION partial | \(O(k^2)\) | $\mathrm{fbs} = \Theta(\mathrm{QC}^2)$ for partial $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{QC} = O(k)$. So the whole block-sensitivity family is capped by a function of $k$ alone, against $\mathrm{R} = \widetilde\Theta(n^{1-1/k})$. |
| Simon's problem partial | \(2\) putative | The fractional relaxation buys nothing: every sensitive block has $\ge 2^{n-1}$ of the $2^n$ coordinates, so $2^{n-1}\sum_B w_B \le \sum_i \mathrm{load}(i) \le 2^n$. |
| Deutsch-Jozsa partial | \(2\) putative | The fractional relaxation buys nothing: every sensitive block has size exactly $N/2$, so a feasible weighting has $\tfrac N2\sum_B w_B = \sum_i \mathrm{load}(i) \le N$. |
| Bernstein-Vazirani partial | \(\Theta(1)\) putative | Exactly $(2^n-1)/2^{n-1} = 2 - 2^{1-n}$. Each block $B_d$ has $2^{n-1}$ elements and each nonzero coordinate $i$ lies in exactly $2^{n-1}$ of the $2^n-1$ blocks, so by symmetry the LP optimum puts weight $2^{1-n}$ on every block. Against $\mathrm{C} = n$ this is an unbounded $\mathrm{C}$-vs-$\mathrm{fbs}$ gap. |
| Unique search partial | \(n\) | Squeezed between $\mathrm{bs} = n$ and $\mathrm{C} = n$. |
| Two-or-none search partial | \(n/2\) putative | Exactly $n/2$ at $0^n$: giving every one of the $\binom n2$ pairs weight $1/(n-1)$ loads each coordinate to exactly $1$ and totals $n/2$, and no assignment beats it, since summing the load over coordinates counts each pair twice, giving $2\sum_B w_B \le n$. |
| Marked bit partial | \(1\) putative | The load constraint at a single existing mark already caps $\sum_B w_B$ at $1$, since every sensitive block contains it. |
| Dense marked bit partial | \(1\) putative | The load constraint at any one of $x$'s marked coordinates already caps $\sum_B w_B$ at $1$, since every sensitive block contains it. |
| Gap-Majority partial | \(\Theta(\min(n, 1/\delta))\) | Same counting, fractionally: $2\delta n\sum_B w_B \le \sum_i\sum_{B \ni i} w_B \le n$. So $\mathrm{fbs} = \Theta(\mathrm{bs}) = O(1)$ at constant $\delta$ while $\mathrm{C} = \Theta(n)$ -- the promise-function counterexample to $\mathrm{C} = O(\mathrm{fbs}^2)$ and to $\mathrm{C} = O(\mathrm{RC}^2)$. |
| Gap-Majority at constant gap partial | \(\Theta(1)\) | At most $1/(2\delta) = 2$ by the counting $2\delta n\sum_B w_B \le n$. So $\mathrm{fbs} = \Theta(1)$ against $\mathrm{C} = \Theta(n)$: the promise counterexample to $\mathrm{C} = O(\mathrm{fbs}^2)$. |
| Parity-labelled FIND-1 partial | \(1\) putative | Between $\mathrm{bs} = 1$ and $\mathrm{C} = 1$. |
| Approximate index partial | \(1\) putative | The load constraint at any single cell of the ball already caps $\sum_B w_B$ at $1$, since every sensitive block contains that cell. |
| Collision problem partial | \(2\) putative | Fractionally the same: $(n/2)\sum_B w_B \le \sum_i \mathrm{load}(i) \le n$. |
| Element distinctness total | \(n\) putative | Between $\mathrm{bs} = n$ and $n$. |
| Ambainis-Belovs function partial | \(O(n)\) | At most $\mathrm{C} = O(n)$. The total-function shortcut $\mathrm{fbs} = \Theta(\mathrm{CA})$ [ABIKPS17] is unavailable on a promise, and the bound $\mathrm{fbs} = O(\widetilde{\deg}^2)$ is recorded only for total $f$, so nothing pins this to $O(1)$ even though $\mathrm{bs} = O(1)$. |
| Surjectivity total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The $\mathrm{s}$ end is itself an unpublished argument (see above), so this is only as good as that. |
| $k$-distinctness total | \(\Theta(n)\) | Between $\mathrm{bs} = \Theta(n)$ and $n$. |
| Triangle finding total | \(\Theta(m^2) = \Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{fbs}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here. |
| Ordered search partial | \(2\) putative | Every "down" block contains position $k$ and every "up" block contains position $k+1$, so the two load constraints alone cap the LP at $2$, which the two unit blocks attain. No fractional gain over $\mathrm{bs}$ here. |
| Inner product mod 2 total | \(n\) | As above. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^2) = \Theta(N^{2/3})\) | Squeezed between $\mathrm{bs} = m^2$ and $\mathrm{C} = m^2$. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here. |
| Scorpion graphs total | \(\Theta(m)\) | Squeezed between $\mathrm{bs}$ and $\mathrm{C}$, both $\Theta(m)$. |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) | Squeezed between $\mathrm{bs}$ and $\mathrm{C}$, both $\Theta(N)$. |
| AND of complemented EXACT-ONE functions total | \(m^2\) | Squeezed between bs and C. KLLPV26 |