Alladi Ramakrishnan Hall

Certificate Games

Anupa Sunny

IRIF, Paris, France

In this talk, we introduce Certificate Game complexity, a new measure of complexity based on the probability of winning a game in which two players are given inputs with different function values and are asked to output some index $i$ where their inputs differ, in a zero communication setting. We study four variants of it, namely those with private coin, public coin, shared entanglement and non-signaling strategies, and place them in the landscape of known complexity measures.

We show that the public coin model is bounded above by randomized query and certificate complexities, while the non signaling model, which is the weakest model we consider, is bounded below by fractional certificate complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. While public coin certificate game complexity is bounded above by randomized query complexity, quantum certificate game complexity can be quadratically larger than quantum query complexity.