Mirror Games Against an Open Book Player

Authors Roey Magen, Moni Naor



PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.20.pdf
  • Filesize: 0.66 MB
  • 12 pages

Document Identifiers

Author Details

Roey Magen
  • Weizmann Institute of Science, Rehovot, Israel
Moni Naor
  • Weizmann Institute of Science, Rehovot, Israel

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 AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. Uriel Feige. A randomized strategy in the mirror game. arXiv preprint arXiv:1901.07809, 2019. Google Scholar
  3. Jacob Fox. Lecture notes for applications of linear algebra, mat 307, combinatorics. URL: https://math.mit.edu/~fox/MAT307-lecture15.pdf.
  4. 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.
  5. 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.
  6. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail