2019/01/23 by Uriel Feige, Feige, Uriel · 1 citation
Computer Science · Mathematics · #Cryptography and Data Security #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1901.07809
openalex publication_date 2019/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Alice and Bob take turns (with Alice playing first) in declaring numbers from the set [1,2N]. If a player declares a number that was previously declared, that player looses and the other player wins. If all numbers are declared without repetition, the outcome is a tie. If both players have unbounded memory and play optimally, then the game will be tied. Garg and Schneider [ITCS 2019] showed that if Alice has unbounded memory, then Bob can secure a tie with log N memory, whereas if Bob has unbounded memory, then Alice needs memory linear in N in order to secure a tie. Garg and Schneider also considered an \em auxiliary matching model in which Alice gets as an additional input a random matching M over the numbers [1,2N], and storing this input does not count towards the memory used by Alice. They showed that is this model there is a strategy for Alice that ties with probability at least 1 - (1)/(N), and uses only O(√(N) (log N)2) memory. We show how to modify Alice's strategy so that it uses only O((log N)3) space.