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

Non-signaling certificate game complexity

Certificate game with arbitrary non-signaling correlations; the weakest of the four.

Definition

As \(\mathrm{CG}(f)\) but the players may use any non-signaling box.

Relations to other measures

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

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

Known values

FunctionValueNotes
OR total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
AND total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
PARITY total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
MAJORITY total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Threshold total \(\Theta(\max\{k,\;n-k+1\})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Symmetric functions (general) total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
EXACT-HALF total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
ODD-MAX-BIT total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
ADDRESS / multiplexer total \(\Theta(k+1)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Binary tree navigation total \(\Theta(k)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
TRIBES total \(\Theta(n/\log n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
AND-OR tree (depth 2) total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Kushilevitz's function (iterated) total \(\Theta(N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Rubinstein's function total \(\Theta(N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Ambainis-Sun function total \(\Theta(N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Meiburg's tournament-subcube function total \(\Theta(14011^{\,d})\) putative All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$, so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim. CGLMSG23
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $f_{2m,m}$: $\mathrm{CG}^{\mathrm{ns}}$, $\mathrm{CG}^*$ and $\mathrm{CG}^{\mathrm{pub}}$ all collapse to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Theta(\sqrt n)$. ABIKPS17
Cheat-sheet functions total \(\widetilde\Theta(\sqrt n)\) Same collapse as the $\mathrm{CG}^{\mathrm{pub}}$ line: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\widetilde\Theta(\sqrt n)$. ABIKPS17
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n)\) Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Omega(n)$. ABIKPS17
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\Theta(n)$. ABIKPS17
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CG}^{\mathrm{pub}})=\Theta(\mathrm{CA})$.
FORRELATION partial \(\widetilde O(\sqrt n)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants; see \(\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 $\mathrm{CG}^{\mathrm{pub}}$ up to constants. CGLMSG23
Simon's problem partial \(\Theta(1)\) Between $1$ and $\mathrm{CG}^{*} = \Theta(1)$.
Deutsch-Jozsa partial \(\Theta(1)\) Between $1$ and $\mathrm{CG}^{*} = \Theta(1)$. CGLMSG23
Bernstein-Vazirani partial \(\Theta(1)\) Between $1$ and $\mathrm{CG}^{*} = \Theta(1)$.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) See $\mathrm{CG}^{*}$. CGLMSG23
Gap-Majority at constant gap partial \(\Theta(1)\) See $\mathrm{CG}^{*}$. CGLMSG23
Approximate index partial \(O(\sqrt{k\log k})\) At most $\mathrm{CG}^{*}$. CGLMSG23
Collision problem partial \(\Theta(1)\) Between $1$ and $\mathrm{CG}^{*}$. CGLMSG23
Element distinctness total \(\Theta(n)\) All three shared-resource variants collapse to $\Theta(\mathrm{CA}) = \Theta(n)$; only private coin can escape, and here it does not.
Ambainis-Belovs function partial \(O(n)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants. CGLMSG23
$k$-distinctness total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Triangle finding total \(\Theta(m^2) = \Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Ordered search partial \(O(\log n)\) As \(\mathrm{CG}^{*}(f)\): $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=O(\log n)$ [CGLMSG23]. Private-coin \(\mathrm{CG}(f)\) is the one variant that escapes the collapse, so it is left blank. CGLMSG23
Inner product mod 2 total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Minsky-Papert one-in-a-box total \(\Theta(m^2) = \Theta(N^{2/3})\) The same non-signaling collapse; see \(\mathrm{CG}^{*}(f)\). CGLMSG23
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) The same non-signaling collapse; see \(\mathrm{CG}^{*}(f)\). CGLMSG23
Scorpion graphs total \(\Theta(m)\) The non-signaling relaxation is already $\Theta(\mathrm{CA}) = \Theta(m)$. CGLMSG23
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) The non-signaling relaxation is already $\Theta(\mathrm{CA}) = \Theta(m^2)$. CGLMSG23