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≠ y_i, in a zerocommunication setting.
We give upper and lower bounds for private coin, public coin, shared entanglement and nonsignaling 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 zeroerror 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 nonsignaling, 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 Θ(√n), then go on to show that this "nonsignaling bottleneck" applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity.
We also consider the singlebit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1. We prove that the singlebit 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 singlebit version of certificate game complexity with private randomness is equal to λ², where λ is the spectral sensitivity.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs.ITCS.2023.32,
author = {Chakraborty, Sourav and G\'{a}l, Anna and Laplante, Sophie and Mittal, Rajat and Sunny, Anupa},
title = {{Certificate Games}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {32:132:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17535},
URN = {urn:nbn:de:0030drops175353},
doi = {10.4230/LIPIcs.ITCS.2023.32},
annote = {Keywords: block sensitivity, boolean function complexity, certificate complexity, query complexity, sensitivity, zerocommunication twoplayer games}
}
Keywords: 

block sensitivity, boolean function complexity, certificate complexity, query complexity, sensitivity, zerocommunication twoplayer games 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 