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+1x. 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 EventownOddtown 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 exponentialsized 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:136:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770958},
ISSN = {18688969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10129},
URN = {urn:nbn:de:0030drops101295},
doi = {10.4230/LIPIcs.ITCS.2019.36},
annote = {Keywords: Mirror Games, Space Complexity, EventownOddtown}
}
Keywords: 

Mirror Games, Space Complexity, EventownOddtown 
Collection: 

10th Innovations in Theoretical Computer Science Conference (ITCS 2019) 
Issue Date: 

2018 
Date of publication: 

08.01.2019 