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

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.

Other measure \(\mathrm{EC}(f)\) in terms of it It in terms of \(\mathrm{EC}(f)\)
\(\mathrm{fbs}(f)\) Fractional block sensitivity total1,2 partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{CA}(f)\) Classical adversary bound total1,2 partial∞ derived open pair → total1,1 partial1,? derived open pair →
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 open pair → total1,2 partial2,? derived open pair →
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) total1,1 partial1,? derived open pair → total2,2 partial2,? open pair →
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity total1,1 partial1,1 derived open pair → total2,2 partial2,? 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\) 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)$.