2026-08-17T12:01:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10129 2024-03-06T10:45:27Z ddc:004 open_access

The Space Complexity of Mirror Games Garg, Sumegha Schneider, Jon Mirror Games Space Complexity Eventown-Oddtown 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}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sumegha Garg and Jon Schneider 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.36 urn:nbn:de:0030-drops-101295 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.36 eng https://creativecommons.org/licenses/by/3.0/legalcode