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

Certificate game complexity (private coin)

Inverse winning probability of a zero-communication game where two players must agree on a coordinate where their inputs differ.

Definition

Two players receive $x$ and $y$ with $f(x)\ne f(y)$ and, without communicating, must both output the same index $i$ with $x_i \ne y_i$. $\mathrm{CG}(f)$ is the inverse of the optimal (worst-case over $(x,y)$) winning probability, using private randomness.

Basic facts

  • $\mathrm{CG}^{\mathrm{ns}} \le \mathrm{CG}^{*} \le \mathrm{CG}^{\mathrm{pub}} \le \mathrm{CG}$. Private coin is the one variant of the four that escapes the collapse to the classical adversary bound [CGLMSG23].
  • The sandwich: $\max\{\mathrm{Adv}(f)^2,\ \mathrm{R}_0(f),\ \mathrm{CA}(f)\} \le \mathrm{CG}(f) \le \min\{\mathrm{C}^0(f)\,\mathrm{C}^1(f),\ O(\mathrm{EC}(f)^2)\}$ [CGLMSG23, Thm 5.10]. For total $f$. The definition itself is stated for possibly-partial $f$, but the sandwich is not: the certificate-product bound needs a $0$-certificate and a $1$-certificate to conflict, and on a promise problem the input stitched together from two non-conflicting certificates may simply be outside the domain. It fails badly there -- \(\mathrm{WT}_n\) has $\mathrm{C} = \Theta(1)$ and $\mathrm{R}_0 = 2^{\Omega(n)}$, so no bound of the form $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ can survive.
  • The upper bound $\mathrm{CG}(f) \le \mathrm{C}^0(f)\,\mathrm{C}^1(f)$ is one line: each player outputs a uniformly random index of a minimal certificate for their own input, and a $0$-certificate and a $1$-certificate must conflict somewhere. It is tight for $\mathrm{OR}$ and for $\oplus$.
  • $\mathrm{CG}$ is not bounded by $\mathrm{D}$: it can exceed the arity of the function. $\mathrm{CG}(\oplus_n) = \Theta(n^2)$, because $\mathrm{C}^0\mathrm{C}^1 = n^2$ above and $\mathrm{Adv}(\oplus_n)^2 = n^2$ below.
  • The single-bit private-coin variant (inputs at Hamming distance $1$) equals $\lambda(f)^2$ [CGLMSG23, Thm 8.9]; the single-bit public-coin variant is $\Theta(\mathrm{s}(f))$ [CGLMSG23, Thm 8.4]. Since restricting the adversary to distance-$1$ pairs can only help the players, these are lower bounds on the unrestricted games.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{CG}(f)\). “\(\mathrm{CG}(f)\) in terms of it” is the pair with \(\mathrm{CG}(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}(f)\) in terms of it It in terms of \(\mathrm{CG}(f)\)
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) total2,4 partial∞ open pair → total1,1 partial1,1 open pair →
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity total2,? partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity total2,? partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{CA}(f)\) Classical adversary bound total2,4 partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{EC}(f)\) Expectational certificate complexity total2,2 partial2,? open pair → total1,1 partial1,? derived open pair →
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity total2,2 partial2,? open pair → total1,1 partial1,? open pair →

The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Sandwiched by the [CGLMSG23] bounds $\max\{\mathrm{Adv}^2, \mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$: here $\mathrm{Adv}^2 = \Theta(n)$ and $\mathrm{R}_0 = n$ from below, and the asymmetric product $\mathrm{C}^0\mathrm{C}^1 = n \cdot 1$ from above. OR is one of the two functions on which the certificate-product bound is tight. Note that the old reading $\mathrm{CG} \le \mathrm{D}$ is not available in general -- $\mathrm{CG}$ is not bounded by the arity -- it just happens to hold here. CGLMSG23
AND total \(\Theta(n)\) Sandwiched by the [CGLMSG23] bounds $\max\{\mathrm{Adv}^2, \mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$: here $\mathrm{Adv}^2 = \Theta(n)$ and $\mathrm{R}_0 = n$ from below, and $\mathrm{C}^0\mathrm{C}^1 = 1 \cdot n$ from above. The mirror image of \(\mathrm{OR}_n\). CGLMSG23
PARITY total \(\Theta(n^2)\) The headline case for this measure: above the arity. From below $\mathrm{CG} \ge \mathrm{Adv}^2 = n^2$ -- equivalently the Hamming-distance-$1$ game already costs $\lambda^2 = n^2$, since two players who differ in one unknown coordinate must each guess it out of $n$ independently. From above $\mathrm{C}^0\mathrm{C}^1 = n^2$. Both [CGLMSG23] bounds are tight on parity, and the result is quadratically larger than $\mathrm{D} = n$: private-coin certificate games are the one variant of the four that is not capped by decision-tree complexity. CGLMSG23
MAJORITY total \(\Theta(n^2)\) Sandwiched between $\mathrm{Adv}^2 = \Theta(n^2)$ and $\mathrm{C}^0\mathrm{C}^1 = \Theta(n^2)$ [CGLMSG23]. Like \(\oplus_n\) this sits above the arity: the sensitivity graph of majority is biregular of degree $\Theta(n)$ between the two middle layers, so $\lambda = \Theta(n)$ and the distance-$1$ game alone already costs $\Theta(n^2)$. CGLMSG23
Threshold total \(\Theta(k(n-k+1))\) Squeezed by the [CGLMSG23] sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$: the upper end is $k(n-k+1)$ and $\mathrm{Adv}^2 = \Theta(k(n-k+1))$ from the \(\mathrm{Adv}(f)\) line above. Interpolates the two recorded endpoints, $\Theta(n)$ for \(\mathrm{OR}_n\) and $\Theta(n^2)$ for \(\mathrm{MAJ}_n\), and shows the whole intermediate range $n^{1+c}$ is realised. CGLMSG23
Symmetric functions (general) total \(\Omega(n),\ O(n^2)\) The [CGLMSG23] sandwich is $\max\{\mathrm{Adv}^2, \mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$, and for a generic non-constant symmetric $f$ only $\mathrm{R}_0 = \Theta(n)$ is available below while $\mathrm{C}^0\mathrm{C}^1 = O(n^2)$ caps it above. Which end is reached depends on the function: it is $\Theta(n)$ for \(\mathrm{OR}_n\) and $\Theta(n^2)$ for \(\oplus_n\) and \(\mathrm{MAJ}_n\), both of which are symmetric, so no single value can be recorded for the whole class. CGLMSG23
EXACT-HALF total \(\Theta(n^2)\) Sandwiched between $\mathrm{Adv}^2 = \Theta(n^2)$ and $\mathrm{C}^0\mathrm{C}^1 = (n/2+1)\cdot n = \Theta(n^2)$ [CGLMSG23]. Above the arity, for the same reason as \(\mathrm{MAJ}_n\): the sensitivity graph is biregular of degree $\Theta(n)$ on the middle slice, so $\lambda = \Theta(n)$. CGLMSG23
ODD-MAX-BIT total \(\Omega(n),\ O(n^2)\) From below $\mathrm{R}_0 = \Theta(n)$ and $\mathrm{Adv}^2 = \Theta(n)$; from above $\mathrm{C}^0\mathrm{C}^1 = \Theta(n^2)$ [CGLMSG23]. The two ends do not meet and nothing in the zoo closes the gap, so the cell is recorded as a range rather than as the old (unjustified) $\Theta(n)$, which rested on the false inequality $\mathrm{CG} \le \mathrm{D}$. CGLMSG23
ADDRESS / multiplexer total \(\Theta(k^2)\) putative Both ends of the [CGLMSG23] sandwich land on $k^2$: $\mathrm{Adv}^2 = \Theta(k^2)$ from below and $\mathrm{C}^0\mathrm{C}^1 = (k+1)^2$ from above. So the address function too has $\mathrm{CG}$ above its own decision-tree complexity $k+1$ -- quadratically so. CGLMSG23
Binary tree navigation total \(\Omega(k),\ O(k^2)\) From below $\mathrm{R}_0 = \Theta(k)$; from above $\mathrm{C}^0\mathrm{C}^1 = k^2$ [CGLMSG23]. No value of $\mathrm{Adv}$ is recorded for this family, so the gap stays open; the previous $\Theta(k)$ rested on the false inequality $\mathrm{CG} \le \mathrm{D}$. CGLMSG23
TRIBES total \(\Theta(n)\) Squeezed by the [CGLMSG23] sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$: below, $\mathrm{Adv}^2 = \Theta(n)$ and $\mathrm{R}_0 = \Theta(n)$; above, $\mathrm{C}^0\mathrm{C}^1 = \Theta(n/\log n)\cdot\Theta(\log n) = \Theta(n)$. The lopsidedness of the two certificate complexities is exactly what makes this cell close, unlike \(\mathrm{OMB}_n\) where the same sandwich leaves a quadratic gap. CGLMSG23
AND-OR tree (depth 2) total \(\Theta(n^2) = \Theta(N)\) putative Pinned by the correct sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1,\ O(\mathrm{EC}^2)\}$ -- note $\mathrm{CG}$ is not capped by $\mathrm{D}$. Lower: $\mathrm{Adv}^2 = \Theta(n^2)$. Upper: $\mathrm{C}^0\mathrm{C}^1 = n\cdot n = n^2$. So the private-coin certificate game costs the full $N$ while the public-coin one costs only $\sqrt N$ -- the \(\mathrm{CG}(f)\) vs \(\mathrm{CG}^{\mathrm{pub}}(f)\) gap is quadratic here.
NAND tree (balanced AND-OR formula) total \(\Theta(N)\) putative Pinned by $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1,\ O(\mathrm{EC}^2)\}$; $\mathrm{CG}$ is not capped by $\mathrm{D}$, but here the two ends meet anyway. Lower: $\mathrm{Adv} = \Theta(\sqrt N)$ gives $\mathrm{Adv}^2 = \Theta(N)$. Upper: $\mathrm{C}^0\mathrm{C}^1 = 2^{\lceil d/2\rceil}2^{\lfloor d/2\rfloor} = 2^d = N$. So the private-coin certificate game costs $\Theta(N)$ while the public-coin one costs $\Theta(\sqrt N)$ and $\mathrm{R}$ costs $N^{0.753\ldots}$.
Recursive MAJORITY-of-3 total \(\Theta(4^{\,d}) = \Theta(N^{1.2619})\) putative Pinned, and far above the arity $N = 3^d$: the private-coin certificate game is not capped by $\mathrm{D}$. Lower: $\mathrm{CG} \ge \mathrm{Adv}^2 = (2^d)^2$. Upper: $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = 2^d\cdot 2^d$. The two meet exactly, so $\mathrm{MAJ}_3^{\circ d}$ is a clean witness for $\mathrm{CG} = \Theta(\mathrm{D}^{1.26})$ -- and for the fact that $\mathrm{CG}$ can exceed $n$.
Kushilevitz's function (iterated) total \(\Omega(N),\ O(N^2)\) Not pinned. The private-coin certificate game is not bounded by $\mathrm{D}$; the correct sandwich is $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1,\ O(\mathrm{EC}^2)\}$. Lower: $\lambda = \sqrt N$ and $\mathrm{Adv} \ge \lambda$, so $\mathrm{Adv}^2 \ge N$ (the $\mathrm{R}_0 = N$ route gives the same). Upper: $\mathrm{C}^0\mathrm{C}^1 = N^2$, and $\mathrm{EC} = N$ gives the same $O(N^2)$. So $\mathrm{CG}$ can be as large as the square of the arity here and only a range is provable.
Rubinstein's function total \(\Omega(N),\ O(N^{3/2})\) Not pinned. The private-coin certificate game is not bounded by $\mathrm{D}$; the correct sandwich is $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1,\ O(\mathrm{EC}^2)\}$. Lower: $\mathrm{Adv}^2 \ge \mathrm{bs} = N/2$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(N)$ says the same. Upper: the two sides are lopsided, $\mathrm{C}^0\mathrm{C}^1 = (N/2)\cdot\sqrt N = \Theta(N^{3/2})$, which beats the $O(\mathrm{EC}^2) = O(N^2)$ route.
Ambainis-Sun function total \(\Omega(N),\ O(N^{3/2})\) putative The private-coin certificate game is not capped by $\mathrm{D}$. Lower: $\mathrm{CG} \ge \mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(N)$. Upper: $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = (6k^2+7k+2)(3k+2) = \Theta(N^{3/2})$, the two sides being wildly asymmetric here. The $\mathrm{EC}$ route gives only $O(\mathrm{EC}^2) = O(N^2)$.
AND composed with NOT-EXACT-HALF total \(\Theta(n^3) = \Theta(N^{3/2})\) Pinned, and above the arity: the private-coin certificate game is not bounded by $\mathrm{D}$. Lower: $\mathrm{Adv} \ge \lambda = \Theta(n^{3/2})$, so $\mathrm{CG} \ge \mathrm{Adv}^2 = \Omega(n^3)$. Upper: $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = n\cdot(n^2/2+n) = \Theta(n^3)$. The two meet, so \(\mathrm{AND}_n \circ \overline{\mathrm{EH}}_n\) is a clean example of $\mathrm{CG} = \Theta(\mathrm{D}^{3/2})$ -- which is exactly what the large $\lambda$ of this function was built to produce.
Meiburg's tournament-subcube function total \(\Omega(14011^{\,d})\) putative The private-coin certificate game is at least $\max\{\mathrm{Adv}^2,\ \mathrm{R}_0,\ \mathrm{CA}\}$, and already $\mathrm{Adv}^2 \ge \mathrm{bs} \ge 14011^{\,d}$. Note $\mathrm{CG}$ is not capped by $\mathrm{D}$, so nothing here is squeezed from above.
Pointer functions total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Variant $f_{2m,m}$. The total-function sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\}\le\mathrm{CG}\le\min\{\mathrm{C}^0\mathrm{C}^1,O(\mathrm{EC}^2)\}$ with $\mathrm{C}^0=\mathrm{C}^1=\mathrm{EC}=\widetilde\Theta(\sqrt n)$ gives the ceiling $\widetilde O(n)$; the floor is $\mathrm{R}_0$ on this variant, which is only $\widetilde\Omega(\sqrt n)$. Private coins are the one escapee from the collapse recorded in the three lines above, so the gap between this line and $\mathrm{CG}^{\mathrm{pub}}$ is genuine and open.
Cheat-sheet functions total \(\widetilde\Theta(n)\) putative Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ gives $\mathrm{CG}=\widetilde\Omega(n)$, and $\mathrm{CG}\le\mathrm{C}^0\mathrm{C}^1=\widetilde O(n)$ gives the matching upper bound.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\widetilde\Omega(n^3)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^2)\) Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\widetilde\Theta(n^2)$; the ceiling is $\mathrm{CG}\le\mathrm{C}^0\mathrm{C}^1=\widetilde O(n^3)$.
Gilmer-Saks-Srinivasan functions total \(\Omega(n^2)\) Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\Theta(n^2)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n)\) Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\widetilde\Theta(n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\widetilde\Theta(n^{2/3})$.
Ambainis' exact-quantum function total \(\Omega(3^d)\) Squeeze: $\mathrm{CG}\ge\mathrm{CG}^{\mathrm{pub}}=\Theta(3^d)$, equally $\mathrm{R}_0=O(\mathrm{CG})$. Only a lower bound is recorded: the ceiling available is $\mathrm{CG}\le\mathrm{C}^0\mathrm{C}^1=\Theta(9^d)$ (or $\mathrm{CG}=O(\mathrm{EC}^2)$, the same), and private randomness is not bounded by $\mathrm{R}_0$ -- $\mathrm{CG}(\oplus_n)=\Theta(n^2)$ while $\mathrm{R}_0(\oplus_n)=n$.
FORRELATION partial \(O(n^{3/2})\) putative Private coins, so no shared index is available and the total-function ceiling $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is not licensed here. Both players output a uniformly random one of the $2n$ positions; since opposite-valued promise inputs differ in $\ge 0.29\sqrt n$ positions the win probability is $\ge 0.29\sqrt n/(2n)^2$, so $\mathrm{CG} = O(n^{3/2})$. From below $\mathrm{CG} \ge \mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA})$, which is only $\Omega(1)$ here.
k-FORRELATION partial \(O(k^2n^2)\) putative Private coins: both players output a uniformly random one of the $kn$ positions and win whenever they collide on a position where the inputs differ, so the win probability is at least $1/(kn)^2$. The total-function ceiling $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is not available on a promise problem. From below only $\mathrm{CG} \ge \mathrm{CG}^{\mathrm{pub}}$.
Simon's problem partial \(O(2^n)\) putative Private coins. An injective $g$ and a two-to-one $g^{\prime}$ must differ on at least $2^{n-1}$ of the $2^n$ table entries: for each of the $2^{n-1}$ pairs $\{x, x\oplus s\}$ we have $g^{\prime}(x)=g^{\prime}(x\oplus s)$ but $g(x)\ne g(x\oplus s)$, so at least one of the two entries moves. Both players output a uniformly random entry, winning with probability $\ge 2^{n-1}/(2^n)^2$. Contrast $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$: this is another unbounded private-versus-public certificate-game gap, as on \(\mathrm{DJ}_n\).
Deutsch-Jozsa partial \(\Theta(N)\) putative The private-coin certificate game is linear here, and the argument is short. Upper: both players output a uniformly random index of $[N]$; when Alice holds a constant $x$ and Bob a balanced $y$ they differ on exactly $N/2$ indices, so they win with probability $(N/2)/N^2 = 1/(2N)$. Lower: fix Alice at $x = 0^N$, where she has a single output distribution $p$. Against a balanced $y$ her success is $\sum_{i \in \mathrm{supp}(y)} p(i)\,q_y(i) \le \max_{i \in \mathrm{supp}(y)} p(i)$. Let $y$ be the indicator of the $N/2$ indices with the smallest $p(i)$: the $(N/2)$-th largest value of $p$ is at most $2/N$, so the value is at most $2/N$ and $\mathrm{CG} \ge N/2$. Note the total-function sandwich $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is not available on a promise problem and is not used. CGLMSG23
Bernstein-Vazirani partial \(\Omega(n),\ O(n^2)\) putative Two players hold the Hadamard codewords of distinct secrets $s \ne s^{\prime}$ and must agree on a position where the tables differ, with private coins only. Upper: both output a uniformly random one of the $n$ positions $e_1,\dots,e_n$; the tables differ at $e_j$ exactly when $s_j \ne s^{\prime}_j$, which happens for some $j$, so they win with probability $\ge 1/n^2$. Lower: fix the first player at $s$ with output distribution $p$ on $\{0,1\}^n$. The $n-1$ heaviest positions span a subspace of dimension $\le n-1$, so some $d \ne 0$ is orthogonal to all of them; against $s^{\prime} = s \oplus d$ the difference set is $\{i : \langle d,i\rangle = 1\}$, which misses all of them, and the win probability is at most the $n$-th largest value of $p$, hence $\le 1/n$. Against $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$ this is another unbounded private-versus-public gap, as on \(\mathrm{DJ}_n\).
Gap-Majority partial \(\Omega(n)\) putative Private coins, and unlike $\mathrm{CG}^{\mathrm{pub}} = \Theta(\min(n,1/\delta))$ it does not shrink with $\delta$. Upper: each player outputs a uniformly random position on which its own input is $1$ (resp. $0$); the two inputs differ on $\ge 2\delta n$ such positions, giving $\mathrm{CG} = O(n/\delta)$. Lower: fix the $1$-player at $x$ with output distribution $p$, and let the $0$-player hold $y$ obtained from $x$ by zeroing the $2\delta n$ positions of $\mathrm{supp}(x)$ carrying the least $p$-mass. The win probability is at most $\max_{i \in \Delta} p(i)$, and the $2\delta n$-th smallest of the $\ge n/2$ values $\{p(i) : x_i = 1\}$ is at most $2/n$. So $\mathrm{CG} \ge n/2$. At constant $\delta$ this is $\Theta(n)$ against $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$: private randomness is the one variant of the four that escapes the collapse to $\mathrm{CA}$.
Gap-Majority at constant gap partial \(\Theta(n)\) putative Private coins, and unlike $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$ it does not shrink with the gap: see the two-sided argument at \(\mathrm{GapMaj}^{\delta}_{n}\).
Approximate index partial \(O(k^2) = O(\log^2 n)\) putative A private-coin strategy, since the total-function sandwich $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is unavailable on a promise problem. Each player, with probability $1/2$, outputs a uniformly random one of the $k$ address bits, and otherwise outputs a random bit of the cell indexed by its own address $a$. If the two addresses differ, they agree on a differing address bit with probability $\ge 1/(4k^2)$; if they are equal, they both name the same cell, which must differ, with probability $\Omega(1)$. So $\mathrm{CG} = O(k^2)$, while $\mathrm{CG}^{\mathrm{pub}} = O(\sqrt{k\log k})$. CGLMSG23
Collision problem partial \(O(n)\) putative Private coins: both players output a uniformly random position, winning with probability $|\Delta|/n^2 \ge 1/(2n)$. The total-function sandwich $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = O(n)$ happens to give the same bound but is not available on a promise problem, so the strategy is the proof. From below only $\Omega(\mathrm{CG}^{\mathrm{pub}}) = \Omega(1)$. CGLMSG23
Element distinctness total \(\Theta(n)\) The sandwich $\max\{\mathrm{Adv}^2, \mathrm{R}_0, \mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1, O(\mathrm{EC}^2)\}$ needs a total function, and this one is total: $\mathrm{R}_0 = \Theta(n)$ below and $\mathrm{C}^0\mathrm{C}^1 = 2n$ above. Note how tight the certificate-product bound is here precisely because the two sides are lopsided -- compare \(\mathrm{forr}\), where the same product is worthless. CGLMSG23
Ambainis-Belovs function partial \(O(n^2)\) putative Private coins: both players output a uniformly random one of the $3n$ positions, winning with probability $\ge 1/(3n)^2$. The sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1, O(\mathrm{EC}^2)\}$ is a total-function statement and is not used here.
Surjectivity total \(\Omega(n),\ O(n^2/\log n)\) The old reading $\mathrm{bs} \le \mathrm{CG} \le \mathrm{D}$ was wrong on the right: $\mathrm{CG}$ is not capped by the arity. The correct sandwich is $\max\{\mathrm{Adv}^2, \mathrm{R}_0, \mathrm{CA}\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23]. Here $\mathrm{R}_0 = \Theta(n)$ from below, and $\mathrm{C}^0\mathrm{C}^1 = \Theta(n/\log n)\cdot\Theta(n)$ from above. The $\mathrm{Adv}$ route gives nothing extra, since only $\mathrm{Adv} = O(n/\sqrt{\log n})$ is recorded. The gap is genuine and left open. CGLMSG23
$k$-distinctness total \(\Theta(n)\) For constant $k$ the correct sandwich $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23] closes: $\mathrm{R}_0 = \Theta(n)$ and $\mathrm{C}^0\mathrm{C}^1 = n \cdot k = \Theta(n)$. The value happens to agree with the one previously recorded, but the old justification -- $\mathrm{CG} \le \mathrm{D}$ -- is false in general: $\mathrm{CG}$ can exceed the arity, as it does for $\oplus_n$. For growing $k$ the ceiling degrades to $O(nk)$. CGLMSG23
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Pinned by $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23]: a $1$-certificate is a single triangle, so $\mathrm{C}^1 = 3$ and the product is $\binom m2 \cdot 3 = \Theta(m^2)$, matching $\mathrm{R}_0 = \Theta(m^2)$ from below. Consistent with $\mathrm{Adv}^2 = \Theta(m^2)$. The lopsided certificate sizes are what make this one of the rare cases where $\mathrm{CG}$ stays at the arity; the old note justified it by the false $\mathrm{CG} \le \mathrm{D}$. CGLMSG23
Inner product mod 2 total \(\Theta(n^2)\) putative Sandwiched: $\mathrm{Adv}(f)^2 \le \mathrm{CG}(f) \le \mathrm{C}^0(f)\,\mathrm{C}^1(f)$ [CGLMSG23], with $\mathrm{Adv} = \Theta(n)$ and $\mathrm{C}^0\mathrm{C}^1 = \Theta(n^2)$ here. Note that this is above the arity: the private-coin game is the one certificate-game variant that is not bounded by $\mathrm{D}$. Inner product behaves exactly like \(\oplus_n\) here, and for the same reason -- distance-$1$ pairs force both players to guess the same index out of $\Theta(n)$ candidates independently. CGLMSG23
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) Pinned by the total-function sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23]: the bottom is $\mathrm{Adv}^2 = \Theta(m^3)$ (equally $\mathrm{R}_0 = \Theta(m^3)$) and the top is $\mathrm{C}^0\mathrm{C}^1 = m^2\cdot m = m^3$. So the private-coin game costs the full $\mathrm{D}$ here, a whole $N^{1/3}$ above the public-coin value $\Theta(m^2)$ -- the largest separation between the two variants that the $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ ceiling permits on this function. CGLMSG23
Sink of a tournament total \(\Omega(m),\ O(m^2)\) The sandwich is $\max\{\mathrm{Adv}^2, \mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23], which here reads $\max\{\Omega(m), \Theta(m)\} \le \mathrm{CG} \le m(m-1)$. It closes to $\Theta(m)$ exactly if $\mathrm{Adv} = \Theta(\sqrt m)$ and to $\Theta(m^2)$ if $\mathrm{Adv} = \Theta(m)$ -- the same open question as the \(\mathrm{Q}_{\varepsilon}(f)\) row of this entry. The old reading $\mathrm{CG} \le \mathrm{D}$ is not available: $\mathrm{CG}$ is not bounded by the arity. CGLMSG23
Scorpion graphs total \(\Omega(m),\ O(m^2)\) The sandwich is $\max\{\mathrm{Adv}^2, \mathrm{R}_0, \mathrm{CA}\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23]: here $\mathrm{R}_0 = \Theta(m)$ from below and $\mathrm{C}^0\mathrm{C}^1 = \Theta(m)\cdot(3m-6) = \Theta(m^2)$ from above, and $\mathrm{Adv}$ is itself only pinned to $[\Omega(\sqrt m), O(m)]$. Note the direction: $\mathrm{R}_0 = O(\mathrm{CG})$, not the reverse -- private coin is the one variant of the game that is harder than zero-error query complexity, and is not capped by $\mathrm{D}$. CGLMSG23
Graph connectivity total \(\Theta(m^3) = \Theta(N^{3/2})\) putative Both ends of the [CGLMSG23] sandwich land on $m^3$: $\mathrm{Adv}(f)^2 = \Theta(m^{3/2})^2 = \Theta(m^3)$ from below, and $\mathrm{C}^0\mathrm{C}^1 = \Theta(m^2)\cdot(m-1) = \Theta(m^3)$ from above. So connectivity is one of the sharpest examples in the zoo of $\mathrm{CG}$ exceeding the arity -- $\mathrm{CG} = \Theta(N^{3/2})$ on $N = \binom{m}{2}$ variables. CGLMSG23