Certificate Games and Consequences for the Classical Adversary Bound

Sourav Chakraborty, Anna Gál, Mika Göös +3

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 va…