Expectational certificate complexity
A relaxation of certificate complexity in which the certificate is a distribution and only expected agreement is required.
Definition
$\mathrm{EC}(f)$ is the smallest $k$ for which there are weight vectors $w^x \in [0,1]^n$ with $\sum_i w^x_i \le k$ for every $x$, and $\sum_{i : x_i \ne y_i} w^x_i w^y_i \ge 1$ for all $x,y$ with $f(x)\ne f(y)$. It sits between fractional block sensitivity and certificate complexity and upper-bounds the classical adversary bound.
Basic facts
- $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$.
- $\mathrm{CG}^{\mathrm{pub}}(f) = O(\mathrm{EC}(f))$ and $\mathrm{CG}(f) = O(\mathrm{EC}(f)^2)$ [CGLMSG23].
- $\mathrm{EC}(f) \le \mathrm{R}_0(f) = O(\mathrm{EC}(f)^2)$ -- the "quadratically tight" relation that motivated the definition [GJKKLSSV17].
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{EC}(f)\). “\(\mathrm{EC}(f)\) in terms of it” is the pair with \(\mathrm{EC}(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\) | Sandwiched between $\mathrm{fbs}=n$ and $\mathrm{C}=n$. GJKKLSSV17 |
| AND total | \(n\) | Sandwiched between $\mathrm{fbs}=n$ and $\mathrm{C}=n$. GJKKLSSV17 |
| PARITY total | \(n\) | Between $\mathrm{fbs}=n$ and $\mathrm{C}=n$. |
| MAJORITY total | \((n+1)/2\) | Same squeeze, since $\mathrm{fbs}\le\mathrm{EC}\le\mathrm{C}$. GJKKLSSV17 |
| Threshold total | \(\max\{k,\;n-k+1\}\) | Squeezed: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, and both ends are $\max\{k,\,n-k+1\}$ here. GJKKLSSV17 |
| Symmetric functions (general) total | \(\Theta(n)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, with both ends $\Theta(n)$ here. GJKKLSSV17 |
| EXACT-HALF total | \(n\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, with both ends $n$ here. GJKKLSSV17 |
| ODD-MAX-BIT total | \(\lfloor n/2 \rfloor + 1\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, with both ends $\lfloor n/2\rfloor+1$ here. GJKKLSSV17 |
| ADDRESS / multiplexer total | \(k+1\) | Between $\mathrm{fbs} = k+1$ and $\mathrm{C} = k+1$. |
| Binary tree navigation total | \(k\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, with both ends $k$ here. GJKKLSSV17 |
| TRIBES total | \(\Theta(n/\log n)\) | Between $\mathrm{fbs}$ and $\mathrm{C}$, which agree up to constants. GJKKLSSV17 |
| AND-OR tree (depth 2) total | \(n\) | Between $\mathrm{fbs}=n$ and $\mathrm{C}=n$. |
| NAND tree (balanced AND-OR formula) total | \(\Theta(\sqrt N)\) | Between $\mathrm{fbs}$ and $\mathrm{C}$, which agree here. |
| Recursive MAJORITY-of-3 total | \(2^d\) | Between $\mathrm{fbs}$ and $\mathrm{C}$. |
| Kushilevitz's function (iterated) total | \(N\) | Between $\mathrm{fbs}=N$ and $\mathrm{C}=N$. |
| Rubinstein's function total | \(\Theta(N)\) | Between $\mathrm{fbs} = \Theta(N)$ and $\mathrm{C} = N/2$. |
| Ambainis-Sun function total | \(\Theta(N)\) | Between $\mathrm{fbs}$ and $\mathrm{C}$, which coincide here. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2)\) | Between $\mathrm{fbs} = \Theta(n^2)$ and $\mathrm{C} = \Theta(n^2)$. |
| Meiburg's tournament-subcube function total | \(14011^{\,d}\) putative | Expectational certificate complexity satisfies $\mathrm{fbs} \le \mathrm{EC} \le \mathrm{C}$, and both ends are exactly $14011^{\,d}$. |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) | Squeezed between $\mathrm{fbs}=\widetilde\Theta(\sqrt n)$ and $\mathrm{C}=\widetilde\Theta(\sqrt n)$ on variant $f_{2m,m}$, which coincide. |
| Cheat-sheet functions total | \(\widetilde\Theta(\sqrt n)\) | Squeezed between $\mathrm{fbs}$ and $\mathrm{C}$, which coincide at $\widetilde\Theta(\sqrt n)$. Against $\mathrm{Q}=\widetilde\Theta(n)$ this is a quadratic $\mathrm{Q}$-vs-$\mathrm{EC}$ gap. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\mathrm{R}_0=O(\mathrm{EC}^2)$ against $\mathrm{R}_0=\widetilde\Omega(n^3)$. This beats the bare $\mathrm{EC}\ge\mathrm{fbs}=\widetilde\Omega(n)$ by half a power. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{4/3})\) | Squeeze: $\mathrm{EC}\ge\mathrm{fbs}=\widetilde\Omega(n^{4/3})$; the ceiling is $\mathrm{EC}\le\mathrm{C}=\widetilde\Theta(n^2)$. (The alternative route $\mathrm{R}_0=O(\mathrm{EC}^2)$ only gives $\widetilde\Omega(n)$.) |
| Gilmer-Saks-Srinivasan functions total | \(\Omega(n)\) | Squeeze: $\mathrm{EC}\ge\mathrm{fbs}=\Theta(n)$, with ceiling $\mathrm{EC}\le\mathrm{C}=\Theta(n^2)$. Note $\mathrm{R}_0=O(\mathrm{EC}^2)$ gives the same $\Omega(n)$, so the two routes agree and neither closes the gap. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{EC}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$ (equally, $\mathrm{R}_0=O(\mathrm{EC}^2)$ with $\mathrm{R}_0=\widetilde\Theta(n)$); the ceiling is $\mathrm{EC}\le\mathrm{C}=\widetilde\Theta(n)$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/3})\) | Squeeze: $\mathrm{EC}\ge\mathrm{fbs}=\widetilde\Omega(n^{1/3})$; the ceiling is $\mathrm{EC}\le\mathrm{C}=\widetilde\Theta(n^{2/3})$. |
| Ambainis' exact-quantum function total | \(\Theta(3^d)\) | Squeeze: $\mathrm{FC}\le\mathrm{EC}\le\mathrm{C}$, and both ends are $3^d$. |
| FORRELATION partial | \(O(n^{3/4})\) putative | Exhibiting a weighting directly, as one must off the promise ($\mathrm{EC} \le \mathrm{C}$ needs totality). Flipping one bit of $x$ or $y$ moves $\Phi$ by at most $2/\sqrt n$, so two promise inputs of opposite value differ in at least $(3/5-1/100)\sqrt n/2 \ge 0.29\sqrt n$ coordinates. Put $w^x_i = (0.29\sqrt n)^{-1/2}$ at every input and every coordinate: then $\sum_{i: x_i \ne y_i} w^x_i w^y_i \ge 1$, and the cost is $2n \cdot \Theta(n^{-1/4}) = \Theta(n^{3/4})$. This beats the trivial $\mathrm{EC} \le \mathrm{C} = \Theta(n)$; from below only $\mathrm{EC} \ge \mathrm{FC} = O(1)$ is available. |
| Simon's problem partial | \(O(2^{n/2})\) putative | Directly, not through $\mathrm{C}$: put $w^g_x = 2^{-(n-1)/2}$ at every one of the $2^n$ points. Two promise inputs of different value differ at $\ge 2^{n-1}$ points (turning a two-to-one $g$ into an injective one requires touching each of its $2^{n-1}$ colliding pairs), so $\sum_{x : g(x)\ne g'(x)} w^g_x w^{g'}_x \ge 1$, and each weight vector sums to $\sqrt 2\,2^{n/2}$. The textbook bound $\mathrm{EC} \le \mathrm{C}$ is a total-function statement and is not used. |
| Deutsch-Jozsa partial | \(\Theta(\sqrt N)\) putative | A genuinely intermediate value, strictly between $\mathrm{fbs} = 2$ and $\mathrm{C} = N/2+1$. Upper: put $w^x_i = 1/\sqrt N$ at the two constant inputs and $w^y_i = 2/\sqrt N$ everywhere at each balanced $y$; a constant $x$ and a balanced $y$ differ on $N/2$ coordinates, giving $\sum_{i : x_i \ne y_i} w^x_i w^y_i = (N/2)(2/N) = 1$, and every weight vector sums to at most $2\sqrt N$. Lower: at $x = 0^N$, for each balanced $y$ we need $1 \le \sum_{i \in \mathrm{supp}(y)} w^x_i w^y_i \le k \max_{i \in \mathrm{supp}(y)} w^x_i$, so fewer than $N/2$ coordinates can have $w^x_i < 1/k$; hence $k \ge \sum_i w^x_i \ge N/(2k)$. |
| Bernstein-Vazirani partial | \(O(n)\) putative | Weight $1$ on each of the $n$ positions $e_1,\dots,e_n$ and $0$ elsewhere, at every input. Two promise inputs with secrets $s \ne s'$ disagree at some $e_j$, since $s$ and $s'$ differ in some coordinate $j$, so the required product $\sum_{i : x_i \ne y_i} w^x_i w^y_i \ge 1$ holds and the scheme costs $n$. From below only $\mathrm{EC} \ge \mathrm{fbs} = \Theta(1)$; note $\mathrm{EC} \le \mathrm{C}$ is a total-function statement and is not what is used here. |
| Gap-Majority partial | \(O(\sqrt{n/\delta})\) putative | Uniform weights $w^x_i = (2\delta n)^{-1/2}$ at every input: two inputs of different value differ in $\ge 2\delta n$ coordinates, so their weighted product is $\ge 1$, at total cost $n/\sqrt{2\delta n} = \sqrt{n/(2\delta)}$. From below $\mathrm{EC} = \Omega(1/\delta)$: given weights of total mass $k$, take $x$ of weight $n/2+\delta n$ and let $\Delta$ be the $2\delta n$ lightest ones of $x$, whose total $w^x$-mass is at most $k\cdot 2\delta n/(n/2) = 4\delta k$; flipping them gives a $0$-input, and the constraint forces $4\delta k \ge 1$. So at constant $\delta$, $\mathrm{EC} = \Omega(1)$ and $O(\sqrt n)$ while $\mathrm{CA} = \Theta(1)$: the textbook chains $\mathrm{EC} \le \mathrm{C}$ and $\mathrm{R}_0 = O(\mathrm{EC}^2)$ are total-function statements and are not used. |
| Gap-Majority at constant gap partial | \(O(\sqrt n)\) putative | Uniform weights $w^x_i = (n/2)^{-1/2}$: two inputs of different value differ in $\ge n/2$ coordinates, so their weighted product is $\ge 1$, at total cost $\sqrt{2n}$. From below $\mathrm{EC} = \Omega(1)$ only, so this cell is not pinned -- but $O(\sqrt n)$ against $\mathrm{C} = \Theta(n)$ already refutes $\mathrm{EC} \le \mathrm{C}$-style tightness and, with $\mathrm{R}_0 = \Theta(n)$, refutes $\mathrm{R}_0 = O(\mathrm{EC}^2)$ on promises. |
| Approximate index partial | \(O(k) = O(\log n)\) putative | Weight $1$ on each of the $k$ address bits and on the two bits of the cell $a$ pointed at by the input's own address. Two inputs of different value with different addresses differ in some address bit, where both put weight $1$; with the same address they differ at cell $a$, which both weight. Cost $k + 2$. This does not go through $\mathrm{EC} \le \mathrm{C} = \Theta(1)$, which is a total-function statement -- its proof needs a $0$-certificate and a $1$-certificate to conflict, and here two non-conflicting certificates stitch together into a string outside the promise. Whether $\mathrm{EC}$ is really $\omega(1)$ here is open; from below only $\mathrm{EC} \ge \mathrm{fbs} = 1$. |
| Collision problem partial | \(O(\sqrt n)\) putative | Uniform weights $w_i = \sqrt{2/n}$: two inputs of different value differ in $\ge n/2$ positions, so their weighted product is $\ge 1$, at cost $\sqrt{2n}$. From below $\mathrm{EC} \ge \mathrm{fbs} = 2$. Not via $\mathrm{EC} \le \mathrm{C}$, which is a total-function statement. |
| Element distinctness total | \(\Theta(n)\) | Squeezed between $\mathrm{fbs} = n$ and $\mathrm{C} = n$. |
| Ambainis-Belovs function partial | \(O(n)\) putative | Exhibited directly, since $\mathrm{EC} \le \mathrm{C}$ needs a total function. Put $w^x_i = 1$ at every input and each of the $3n$ variables: any two inputs of different value differ somewhere, so $\sum_{i : x_i \ne y_i} w^x_i w^y_i \ge 1$, at cost $3n$. |
| Surjectivity total | \(\Theta(n)\) | Squeezed between $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, both $\Theta(n)$ here. |
| $k$-distinctness total | \(\Theta(n)\) | Squeezed between $\mathrm{fbs} = \Theta(n)$ and $\mathrm{C} = n$. |
| Triangle finding total | \(\Theta(m^2) = \Theta(n)\) | Squeezed between $\mathrm{fbs} = \Theta(m^2)$ and $\mathrm{C} = \binom m2$. |
| Ordered search partial | \(O(\sqrt n)\)· putative | Put $w^{x^{(k)}}_i=1/\sqrt{k+1-i}$ for $i\le k$ and $1/\sqrt{i-k}$ for $i>k$, so every weight is in $[0,1]$ and $\sum_iw^x_i\le4\sqrt n$. Two promise inputs $k$ and $k+d$ have different values only for odd $d$, and they differ exactly on the $d$ coordinates between them, where $\sum_{t=1}^{d}1/\sqrt{t(d+1-t)}\ge1$ (equality at $d=1$, tending to $\pi$). The certificate weighting is not available: the $d=1$ constraints force $w^{x^{(k)}}_k=w^{x^{(k)}}_{k+1}=1$, and supports two apart then fail to overlap. The total-function bound $\mathrm{EC}\le\mathrm{C}=2$ does not hold on a promise. |
| Inner product mod 2 total | \(n\) | Between $\mathrm{fbs} = n$ and $\mathrm{C} = n$. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^2) = \Theta(N^{2/3})\) | Squeezed between $\mathrm{fbs} = \Theta(m^2)$ and $\mathrm{C} = m^2$. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Between $\mathrm{fbs}(f) = \mathrm{FC}(f) \le \mathrm{EC}(f)$ and $\mathrm{EC}(f) \le \mathrm{C}(f)$, both $\Theta(m)$ here. |
| Scorpion graphs total | \(\Theta(m)\) | Between $\mathrm{fbs}(f) = \mathrm{FC}(f) \le \mathrm{EC}(f)$ and $\mathrm{EC}(f) \le \mathrm{C}(f)$, both $\Theta(m)$ here. |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) | Squeezed between $\mathrm{fbs} = \Theta(m^2)$ and $\mathrm{C} = \Theta(m^2)$. |