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

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

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.

Other measure \(\mathrm{fbs}(f)\) in terms of it It in terms of \(\mathrm{fbs}(f)\)
\(\mathrm{bs}(f)\) Block sensitivity total1.5,2 partial1.5,? open pair → total1,1 partial1,1 open pair →
\(\mathrm{RC}(f)\) Randomized certificate complexity total1,1 partial1,1 open pair → total1,1 partial1,1 open pair →
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 open pair → total2,2 partial∞ open pair →
\(\mathrm{CA}(f)\) Classical adversary bound total1,1 partial1,? open pair → total1,1 partial1,? open pair →
\(\mathrm{FC}(f)\) Fractional certificate complexity total1,1 partial1,1 open pair → total1,1 partial1,1 open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total2,2 partial2,2 derived open pair → total2,3 partial∞ derived 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\) 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