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
- \(\mathrm{CA}(f)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ CGLMSG23
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.
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 | \(\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 |