LIPIcs.FUN.2022.20.pdf
- Filesize: 0.66 MB
- 12 pages
Document
Mirror Games Against an Open Book Player
Authors
-
Part of:
Volume:
11th International Conference on Fun with Algorithms (FUN 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-05-23
File
Document Identifiers
Acknowledgements
We thank Boaz Menuhin for very useful discussions and comments and thank Ehud Friedgut for discussions concerning an extension of Berlekamp’s Theorem. We thank the anonymous referees for numerous helpful comments.
Cite As Get BibTex
Roey Magen and Moni Naor. Mirror Games Against an Open Book Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.20
Abstract
Mirror games were invented by Garg and Schnieder (ITCS 2019). Alice and Bob take turns (with Alice playing first) in declaring numbers from the set {1,2, …, 2n}. If a player picks a number that was previously played, that player loses and the other player wins. If all numbers are declared without repetition, the result is a draw. Bob has a simple mirror strategy that assures he won't lose and requires no memory. On the other hand, Garg and Schenier showed that every deterministic Alice needs memory of size linear in n in order to secure a draw.
Regarding probabilistic strategies, previous work showed that a model where Alice has access to a secret random perfect matching over {1,2, …, 2n} allows her to achieve a draw in the game w.p. a least 1-1/n and using only polylog bits of memory.
We show that the requirement for secret bits is crucial: for an "open book" Alice with no secrets (Bob knows her memory but not future coin flips) and memory of at most n/4c bits for any c ≥ 2, there is a Bob that wins w.p. close to 1-{2^{-c/2}}.
Subject Classification
ACM Subject Classification
- Theory of computation → Streaming models
Keywords
- Mirror Games
- Space Complexity
- Eventown-Oddtown
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 63-80. ACM, 2020. URL: https://doi.org/10.1145/3375395.3387658.
-
Uriel Feige. A randomized strategy in the mirror game. arXiv preprint arXiv:1901.07809, 2019.
- Jacob Fox. Lecture notes for applications of linear algebra, mat 307, combinatorics. URL: https://math.mit.edu/~fox/MAT307-lecture15.pdf.
- Sumegha Garg and Jon Schneider. The space complexity of mirror games. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 36:1-36:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.36.
- Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Advances in Cryptology - CRYPTO 2021, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, pages 94-121. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-84252-9_4.
- Boaz Menuhin and Moni Naor. Keep that card in mind: Card guessing with limited memory. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 107:1-107:28. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.107.