All reports by Author Anupa Sunny:

__
TR22-143
| 7th November 2022
__

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny#### Certificate games

Revisions: 1

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny

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 ... more >>>