License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.36
URN: urn:nbn:de:0030-drops-101295
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10129/
Garg, Sumegha ;
Schneider, Jon
The Space Complexity of Mirror Games
Abstract
We consider the following game between two players Alice and Bob, which we call the mirror game. Alice and Bob take turns saying numbers belonging to the set {1, 2, ...,N}. A player loses if they repeat a number that has already been said. Otherwise, after N turns, when all the numbers have been spoken, both players win. When N is even, Bob, who goes second, has a very simple (and memoryless) strategy to avoid losing: whenever Alice says x, respond with N+1-x. The question is: does Alice have a similarly simple strategy to win that avoids remembering all the numbers said by Bob?
The answer is no. We prove a linear lower bound on the space complexity of any deterministic winning strategy of Alice. Interestingly, this follows as a consequence of the Eventown-Oddtown theorem from extremal combinatorics. We additionally demonstrate a randomized strategy for Alice that wins with high probability that requires only O~(sqrt N) space (provided that Alice has access to a random matching on K_N).
We also investigate lower bounds for a generalized mirror game where Alice and Bob alternate saying 1 number and b numbers each turn (respectively). When 1+b is a prime, our linear lower bounds continue to hold, but when 1+b is composite, we show that the existence of a o(N) space strategy for Bob (when N != 0 mod (1+b)) implies the existence of exponential-sized matching vector families over Z^N_{1+b}.
BibTeX - Entry
@InProceedings{garg_et_al:LIPIcs:2018:10129,
author = {Sumegha Garg and Jon Schneider},
title = {{The Space Complexity of Mirror Games}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {36:1--36:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-095-8},
ISSN = {1868-8969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10129},
URN = {urn:nbn:de:0030-drops-101295},
doi = {10.4230/LIPIcs.ITCS.2019.36},
annote = {Keywords: Mirror Games, Space Complexity, Eventown-Oddtown}
}
|
Keywords: |
|
Mirror Games, Space Complexity, Eventown-Oddtown |
|
Collection: |
|
10th Innovations in Theoretical Computer Science Conference (ITCS 2019) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.01.2019 |
