Certificate Games and Consequences for the Classical Adversary Bound
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 ve...
Guardat en:
| Autors principals: | , , , , , |
|---|---|
| Format: | Article |
| Publicat: |
2022
|
| Matèries: | |
| Accés en línia: | https://arxiv.org/abs/2211.03396 http://arxiv.org/abs/2211.03396 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|