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
- \(\mathrm{fbs}(f)\) $\mathrm{FC}(f) = \mathrm{fbs}(f)$ exactly, by LP duality Tal13 KulkarniTal16 Aaronson08
- \(\mathrm{RC}(f)\) $\mathrm{FC}(f) = \Theta(\mathrm{RC}(f))$ Aaronson08 KulkarniTal16
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.
The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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. |