Q The Query Complexity Zoo
\(\mathrm{CG}^{\mathrm{pub}}(f)\)

Certificate game complexity (public coin)

Public-coin version of the certificate game; equals the classical adversary bound.

Definition

As \(\mathrm{CG}(f)\) but the players share randomness.

Basic facts

  • $\mathrm{fbs}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \min(\mathrm{EC}(f), \mathrm{RS}(f), \mathrm{C}(f))$ up to constants.
  • $\mathrm{CG}^{\mathrm{pub}}(f) = O(\mathrm{R}(f))$.
  • The single-bit public-coin variant $= \Theta(\mathrm{s}(f))$, a new characterisation of sensitivity.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{CG}^{\mathrm{pub}}(f)\). “\(\mathrm{CG}^{\mathrm{pub}}(f)\) in terms of it” is the pair with \(\mathrm{CG}^{\mathrm{pub}}(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{CG}^{\mathrm{pub}}(f)\) in terms of it It in terms of \(\mathrm{CG}^{\mathrm{pub}}(f)\)
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) total1,1 partial1,1 open pair → total2,4 partial∞ open pair →
\(\mathrm{CA}(f)\) Classical adversary bound total1,1 partial1,1 open pair → total1,1 partial1,1 open pair →
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity total1,? partial1,? open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{fbs}(f)\) Fractional block sensitivity total1,1 partial1,? derived open pair → total1,1 partial1,? derived open pair →
\(\mathrm{s}(f)\) Sensitivity total2.1308,4 partial∞ derived open pair → total1,1 partial1,1 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 \(\Theta(n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(n)$ and $\mathrm{fbs}(f) = n$ here.
AND total \(\Theta(n)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{RC}(f)$, with $\mathrm{fbs}(f) = n$ and $\mathrm{RC}(f) = \Theta(n)$ here.
PARITY total \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
MAJORITY total \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{RC}(f)$, with both ends $\Theta(n)$ here.
Threshold total \(\Theta(\max\{k,\;n-k+1\})\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \max\{k,\;n-k+1\}$ here.
Symmetric functions (general) total \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ for every $f$, and $\mathrm{CA}(f) = \Theta(n)$ here. CGLMSG23
EXACT-HALF total \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
ODD-MAX-BIT total \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ for every $f$, and $\mathrm{CA}(f) = \Theta(n)$ here. CGLMSG23
ADDRESS / multiplexer total \(\Theta(k+1)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = k+1$ here.
Binary tree navigation total \(\Theta(k)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ for every $f$, and $\mathrm{CA}(f) = \Theta(k)$ here. CGLMSG23
TRIBES total \(\Theta(n/\log n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{fbs}(f)$, with both ends $\Theta(n/\log n)$ here.
AND-OR tree (depth 2) total \(\Theta(n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(n)$ and $\mathrm{fbs}(f) = n$ here.
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{RC}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{RC}(f) = \Theta(\sqrt{N})$ here.
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = 2^d$ here.
Kushilevitz's function (iterated) total \(\Theta(N)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(N)$ and $\mathrm{fbs}(f) = N$ here.
Rubinstein's function total \(\Theta(N)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(N)$ here.
Ambainis-Sun function total \(\Theta(N)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(N)$ here.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\Theta(14011^{\,d})\) putative $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{fbs})$ for every total $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and \(\mathrm{fbs}(f)\) is pinned at $14011^{\,d}$.
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $f_{2m,m}$: the public-coin certificate game value collapses to $\Theta(\mathrm{CA})$, and $\mathrm{CA}=\Theta(\mathrm{fbs})=\widetilde\Theta(\sqrt n)$ for total functions [ABIKPS17]. ABIKPS17
Cheat-sheet functions total \(\widetilde\Theta(\sqrt n)\) The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Theta(\sqrt n)$ for total functions [ABIKPS17]. Read against the recorded $\mathrm{CG}=\widetilde\Theta(n)$, this family is a quadratic separation of private-coin from public-coin certificate games -- private coins are the one escapee from the collapse $\mathrm{CG}^{\mathrm{ns}}=\mathrm{CG}^*=\mathrm{CG}^{\mathrm{pub}}=\Theta(\mathrm{CA})$. ABIKPS17
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n)\) The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Omega(n)$ for total functions [ABIKPS17]. Against the recorded $\mathrm{CG}=\widetilde\Omega(n^3)$ this cell is where the private-coin/public-coin gap would show, but only the two floors are known. ABIKPS17
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$ for total functions [ABIKPS17], whose recorded range is $[\widetilde\Omega(n^{4/3}),\widetilde O(n^2)]$; independently $\mathrm{CG}^{\mathrm{pub}}\le\mathrm{C}=\widetilde\Theta(n^2)$. ABIKPS17
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\Theta(n)$ for total functions [ABIKPS17]. Against the recorded $\mathrm{CG}=\Omega(n^2)$ this makes the family a quadratic private-coin-vs-public-coin certificate-game separation with no logarithmic loss. ABIKPS17
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Omega(\sqrt n)$ for total functions [ABIKPS17]; the ceiling is $\mathrm{CG}^{\mathrm{pub}}\le\mathrm{C}=\widetilde\Theta(n)$. Against the recorded $\mathrm{CG}=\widetilde\Omega(n)$ this is where a private-coin/public-coin gap could appear. ABIKPS17
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Omega(n^{1/3})$ for total functions [ABIKPS17]; the ceiling is $\mathrm{CG}^{\mathrm{pub}}\le\mathrm{C}=\widetilde\Theta(n^{2/3})$. ABIKPS17
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: $\mathrm{CG}^{\mathrm{pub}}=\Theta(\mathrm{CA})$.
FORRELATION partial \(\widetilde O(\sqrt n)\) The public-coin, entangled and non-signaling certificate games all collapse to $\Theta(\mathrm{CA})$ (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)). CGLMSG23
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) Equal to $\Theta(\mathrm{CA})$; the public-coin, entangled and non-signaling games all collapse there. CGLMSG23
Simon's problem partial \(\Theta(1)\) putative The shared-randomness strategy needs nothing but the code distance: both players output the same uniformly random point $x$ of the domain of $g$, and win iff $g(x) \ne g'(x)$. Two promise inputs of different value differ at $\ge 2^{n-1}$ of the $2^n$ points, so this wins with probability $\ge 1/2$ and $\mathrm{CG}^{\mathrm{pub}} \le 2$. In general $\mathrm{CG}^{\mathrm{pub}}(f) \le n/d$ where $d$ is the least Hamming distance between two domain points of different value. CGLMSG23
Deutsch-Jozsa partial \(\Theta(1)\) One shared random index $i$, output by both players, already wins with probability $1/2$. So $\mathrm{CG}^{\mathrm{pub}} \le 2$, matching $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA}) = \Theta(1)$. Against $\mathrm{CG} = \Theta(N)$ this is an unbounded private-versus-public certificate game gap on a partial function: shared randomness is what lets the two players agree on where to look. CGLMSG23
Bernstein-Vazirani partial \(\Theta(1)\) putative Both players output the same uniformly random position $i \in [2^n]$; they win iff $x_i \ne y_i$, which for two distinct Hadamard codewords happens with probability exactly $1/2$. So $\mathrm{CG}^{\mathrm{pub}} \le 2$, and $\ge 1$ trivially. (In general $\mathrm{CG}^{\mathrm{pub}}(f) \le N/d$ for $d$ the minimum Hamming distance between differently-valued inputs.) CGLMSG23
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) putative Both players output the same uniformly random index. Inputs of different value differ in at least $2\delta n$ of the $n$ coordinates, so they win with probability $\ge 2\delta$ and $\mathrm{CG}^{\mathrm{pub}} \le 1/(2\delta)$; and $\mathrm{CG}^{\mathrm{pub}} \ge \mathrm{fbs}$. CGLMSG23
Gap-Majority at constant gap partial \(\Theta(1)\) putative Both players output the same uniformly random index; inputs of different value differ in $\ge n/2$ coordinates, so they win with probability $\ge 1/2$. CGLMSG23
Approximate index partial \(O(\sqrt{k\log k})\) $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA}) = O(\mathrm{R})$; the shared-randomness version of the strategy in $\mathrm{CG}$ also gives $O(k)$. From below only $\Omega(\mathrm{fbs}) = \Omega(1)$. CGLMSG23
Collision problem partial \(\Theta(1)\) putative Both players output the same uniformly random position $i$. A two-to-one $g$ and a one-to-one $g'$ can agree only on a set where $g$ is injective, i.e. on at most one point of each of the $n/2$ pairs, so they differ on $\ge n/2$ positions and the strategy wins with probability $\ge 1/2$. Hence $\mathrm{CG}^{\mathrm{pub}} \le 2$, and $\ge \mathrm{fbs} = 2$. CGLMSG23
Element distinctness total \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA}) = \Theta(n)$. Unlike the promise problems in this file, the public-coin game gains nothing over the private-coin one here. CGLMSG23
Ambainis-Belovs function partial \(O(n)\) $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA}) = O(n)$ -- the LP-duality collapse survives a promise. Directly: on a shared random one of the $3n$ positions the players win with probability $\ge 1/(3n)$. CGLMSG23
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
$k$-distinctness total \(\Theta(n)\) Squeezed between $\mathrm{fbs} = \Theta(n)$ and $\mathrm{C} = n$; equivalently $\Theta(\mathrm{CA})$, which is also $\Theta(n)$ here. CGLMSG23
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
Ordered search partial \(O(\log n)\) $\mathrm{CG}^{\mathrm{pub}}=\Theta(\mathrm{CA})$ survives the passage to partial functions [CGLMSG23], and \(\mathrm{CA}(f)\) is $O(\log n)$. CGLMSG23
Inner product mod 2 total \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^2) = \Theta(N^{2/3})\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ for every $f$ [CGLMSG23], and $\mathrm{CA} = \Theta(m^2)$ here. CGLMSG23
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CG}^{*}) = \Theta(\mathrm{CG}^{\mathrm{ns}}) = \Theta(\mathrm{CA})$, the non-signaling bottleneck [CGLMSG23], and $\mathrm{CA} = \Theta(m)$ here. CGLMSG23
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CG}^{*}) = \Theta(\mathrm{CG}^{\mathrm{ns}}) = \Theta(\mathrm{CA})$, the non-signaling bottleneck [CGLMSG23], and $\mathrm{CA} = \Theta(m^2)$ here. CGLMSG23