2022/04/26 by Roey Magen, Magen, Roey, Moni Naor +1 · 1 citation
Computer Science · #Authorship Attribution and Profiling #Chaos-based Image/Signal Encryption #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #User Authentication and Security Systems
paper · pdf · doi:10.48550/arxiv.2204.12129
openalex publication_date 2022/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.