Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR22-143 | 10th March 2025 22:03

Certificate games

RSS-Feed




Revision #2
Authors: Sourav Chakraborty, Anna Gal, Mika Göös, Sophie Laplante, Rajat Mittal, Anupa Sunny
Accepted on: 10th March 2025 22:03
Downloads: 12
Keywords: 


Abstract:

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We study four versions of certificate games, namely private coin, public coin, shared entanglement and non-signaling games. The public-coin variant of certificate games gives a new characterization of the classical adversary bound, a lower bound on randomized query complexity which was introduced as a classical version of the quantum (non-negative) quantum adversary bound.

We show that complexity in the public coin model (therefore also the classical adversary) is bounded above by certificate complexity, as well as by expectational certificate complexity and sabotage complexity. On the other hand, it is bounded below by fractional and randomized certificate complexity.

The quantum measure reveals an interesting and surprising difference between classical and quantum query models: the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of $n$ on the quantum certificate game complexity of the $\OR$ function, whose quantum query complexity is $\Theta(\sqrt{n})$, then go on to show that this ``non-signaling bottleneck'' applies to all functions with high sensitivity, block sensitivity, fractional block sensitivity, as well as classical adversary. This implies the collapse of all models of certificate games, except private randomness, to the classical adversary bound.

We consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1, and give a new characterization of sensitivity and spectral sensitivity.



Changes to previous version:

Major update of the previous version.
Title updated from Certificate Games
Author added: Mika Goos


Revision #1 to TR22-143 | 11th November 2022 06:54

Certificate games





Revision #1
Authors: Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny
Accepted on: 11th November 2022 06:54
Downloads: 405
Keywords: 


Abstract:

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations.
We show that complexity in the public coin model is upper bounded by Randomized query and Certificate complexity. On the other hand, it is lower bounded by fractional and randomized certificate complexity, making it a good candidate to prove strong lower bounds on randomized query complexity.
Complexity in the private coin model is bounded from below by zero-error randomized query complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. Whereas the public coin certificate game complexity is bounded from above by randomized query complexity, the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of $n$ on the quantum certificate game complexity of the OR function, whose quantum query complexity is $\Theta(\sqrt{n})$, then go on to show that this ``non-signaling bottleneck'' applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity.

We also consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance $1$. We prove that the single-bit version of certificate game complexity with shared randomness is equal to sensitivity up to constant factors, thus giving a new characterization of sensitivity. On the other hand, the single-bit version of certificate game complexity with private randomness is equal to $\lambda^2$, where $\lambda$ is the spectral sensitivity.



Changes to previous version:

fixed a typo


Paper:

TR22-143 | 7th November 2022 09:51

Certificate games


Abstract:

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations.
We show that complexity in the public coin model is upper bounded by Randomized query and Certificate complexity. On the other hand, it is lower bounded by fractional and randomized certificate complexity, making it a good candidate to prove strong lower bounds on randomized query complexity.
Complexity in the private coin model is bounded from below by zero-error randomized query complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. Whereas the public coin certificate game complexity is bounded from above by randomized query complexity, the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of $n$ on the quantum certificate game complexity of the OR function, whose quantum query complexity is $\Theta(\sqrt{n})$, then go on to show that this ``non-signaling bottleneck'' applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity.

We also consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance $1$. We prove that the single-bit version of certificate game complexity with shared randomness is equal to sensitivity up to constant factors, thus giving a new characterization of sensitivity. On the other hand, the single-bit version of certificate game complexity with private randomness is equal to $\lambda^2$, where $\lambda$ is the spectral sensitivity.



ISSN 1433-8092 | Imprint