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

Fractional certificate complexity

LP relaxation of certificate complexity: fractional weights on coordinates that must cover every disagreement.

also written: fractional vertex cover of the sensitive blocks, \mathrm{C}^{*}(f), LP certificate complexity

Definition

$\mathrm{FC}_x(f)$ is the value of the linear program $$\min \sum_{i\in[n]} w_i \quad\text{s.t.}\quad \sum_{i\,:\,x_i \ne y_i} w_i \ \ge\ 1 \ \ \forall\, y \in \mathrm{Dom}(f) \text{ with } f(y)\ne f(x), \qquad w \in [0,1]^n ,$$ and $\mathrm{FC}(f) = \max_x \mathrm{FC}_x(f)$. Setting $w$ to the indicator of a certificate is feasible, so this is the LP relaxation of $\mathrm{C}_x(f)$.

The dual LP puts weights on sensitive blocks subject to each coordinate receiving total weight at most $1$ -- that is exactly \(\mathrm{fbs}(f)\). Both LPs are feasible and bounded, so strong duality gives $$\mathrm{FC}_x(f) = \mathrm{fbs}_x(f) \quad\text{for every } x,$$ an equality, not a $\Theta$. The zoo keeps the two names as separate entries because the literature uses them for different purposes: $\mathrm{fbs}$ when lower-bounding something by exhibiting blocks, $\mathrm{FC}$ when upper-bounding something by exhibiting a fractional certificate (this is the form in which it feeds $\mathrm{R}_0 = O(\mathrm{FC}\cdot\log)$-style rounding arguments and the quantum certificate bound $\mathrm{QC} = \Theta(\sqrt{\mathrm{FC}})$).

Basic facts

  • $\mathrm{bs}(f) \le \mathrm{FC}(f) = \mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$.
  • $\mathrm{C}(f) = O(\mathrm{FC}(f)^2)$ by randomised rounding, and the quadratic loss is real [GSS16].
  • $\mathrm{FC}(f) = O(\widetilde{\deg}(f)^2)$ [KulkarniTal16].
  • For monotone $f$, $\mathrm{FC}(f) = \mathrm{C}(f)$: the LP has an integral optimum.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{FC}(f)\). “\(\mathrm{FC}(f)\) in terms of it” is the pair with \(\mathrm{FC}(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{FC}(f)\) in terms of it It in terms of \(\mathrm{FC}(f)\)
\(\mathrm{fbs}(f)\) Fractional block sensitivity total1,1 partial1,1 open pair → total1,1 partial1,1 open pair →
\(\mathrm{RC}(f)\) Randomized certificate complexity total1,1 partial1,1 derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 derived open pair → total2,2 partial∞ derived open pair →
\(\mathrm{EC}(f)\) Expectational certificate complexity total1,1 partial1,1 open pair → total1,2 partial∞ derived open pair →
\(\mathrm{QC}(f)\) Quantum certificate complexity total2,2 partial2,2 derived open pair → total0.5,0.5 partial0.5,0.5 derived open pair →

The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(n\) Equal to $\mathrm{fbs}$ by LP duality; the LP is integral here because at $0^n$ every coordinate must carry weight $1$. Aaronson08
AND total \(n\)
PARITY total \(n\)
MAJORITY total \((n+1)/2\) Equal to $\mathrm{fbs}$.
Threshold total \(\max\{k,\;n-k+1\}\) Equal to $\mathrm{fbs}$ by LP duality.
Symmetric functions (general) total \(\Theta(n)\) $\mathrm{FC}(f) = \mathrm{fbs}(f)$ exactly, by LP duality. Tal13
EXACT-HALF total \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
ODD-MAX-BIT total \(\lfloor n/2 \rfloor + 1\) $\mathrm{FC}(f) = \mathrm{fbs}(f)$ exactly, by LP duality. Tal13 KulkarniTal16
ADDRESS / multiplexer total \(k+1\) Equal to $\mathrm{fbs}$ by LP duality.
Binary tree navigation total \(k\) $\mathrm{FC}(f) = \mathrm{fbs}(f)$ exactly, by LP duality, and $\mathrm{fbs} = k$ here. Tal13 KulkarniTal16
TRIBES total \(\Theta(n/\log n)\) Equal to $\mathrm{fbs}$ by LP duality.
AND-OR tree (depth 2) total \(n\)
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt N)\) Equal to $\mathrm{fbs}$ by LP duality.
Recursive MAJORITY-of-3 total \(2^d\) Equal to $\mathrm{fbs}$ by LP duality.
Kushilevitz's function (iterated) total \(N\)
Rubinstein's function total \(\Theta(N)\) Equal to $\mathrm{fbs}$ by LP duality.
Ambainis-Sun function total \(6k^2+7k+2\) $\mathrm{FC} = \mathrm{fbs}$ by LP duality, and \(\mathrm{fbs}(f)\) is pinned at $(3k+2)(2k+1)$ here.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(14011^{\,d}\) putative $\mathrm{FC} = \mathrm{fbs}$ by LP duality, and \(\mathrm{fbs}(f)\) is pinned at $14011^{\,d}$.
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
Cheat-sheet functions total \(\widetilde\Theta(\sqrt n)\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n)\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
Random-indicator gadget total \(n\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3})\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
FORRELATION partial \(O(1)\) Equal to $\mathrm{fbs}$ by LP duality.
k-FORRELATION partial \(O(k^2)\) Equal to $\mathrm{fbs}$ by LP duality.
Simon's problem partial \(2\) Equal to $\mathrm{fbs}$ by LP duality.
Deutsch-Jozsa partial \(\Theta(1)\) Equal to $\mathrm{fbs} = 2$ by LP duality; also $\le \mathrm{R} = O(1)$.
Bernstein-Vazirani partial \(\Theta(1)\) Equal to $\mathrm{fbs}$ by LP duality.
Marked bit partial \(1\) Equal to $\mathrm{fbs}$ by LP duality.
Dense marked bit partial \(1\) Equal to $\mathrm{fbs}$ by LP duality.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) Equal to $\mathrm{fbs}$ by LP duality.
Gap-Majority at constant gap partial \(\Theta(1)\) Equal to $\mathrm{fbs}$ by LP duality.
Parity-labelled FIND-1 partial \(1\) putative Weight $1$ on a single $i \in \mathrm{supp}(x)$ is feasible -- every $y$ of the opposite value differs from $x$ at $i$ -- and $\mathrm{FC} \ge \mathrm{fbs} = 1$.
Approximate index partial \(1\) Equal to $\mathrm{fbs}$ by LP duality.
Collision problem partial \(2\) Equal to $\mathrm{fbs}$ by LP duality.
Element distinctness total \(n\) Equal to $\mathrm{fbs}$ by LP duality.
Ambainis-Belovs function partial \(O(n)\) Equal to $\mathrm{fbs}$ by LP duality.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{FC}(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)\) Equal to $\mathrm{fbs}$ by LP duality.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{FC}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
Ordered search partial \(2\) putative Equal to $\mathrm{fbs}$ by LP duality.
Inner product mod 2 total \(n\) Sandwiched: $\mathrm{s}(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^2) = \Theta(N^{2/3})\) $\mathrm{FC} = \mathrm{fbs}$ exactly, by LP duality, and $\mathrm{fbs} = \Theta(m^2)$ here.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) $\mathrm{FC} = \mathrm{fbs}$ exactly, by LP duality, and $\mathrm{fbs} = \Theta(m)$ here.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) $\mathrm{FC} = \mathrm{fbs}$ exactly, by LP duality, and $\mathrm{fbs} = \Theta(m^2)$ here.