Abstract
A single-player Memory Game starts with n pairs of identical cards facing down, with a picture drawn on the face of each card. There are n distinct pictures: the two cards in each pair have the same picture. Each operation in the game reveals two cards. If these cards match, i.e., they have the same picture, then the player takes them away; otherwise the cards are turned back to face down. The object of the game is to clear all cards as quickly as possible. Past works have thoroughly studied the expected number of moves required, assuming optimal play, but these works assume that the player has perfect memory. Let T be the number of operations required to clear all cards when the player has only S bits of memory. A little thought shows that a tradeoff upper bound of ST = O(n^2 log n) is achievable. In our work, we study corresponding lower bounds. We prove that ST = Omega(n^2) in a restricted model where the player may only compare cards for equality and cannot perform any computations on the pictures. We further prove that ST^2 = Omega(n^3) without any such restrictions, assuming only that each picture can be represented as an integer in {1,2,...,R}. We do this by studying the problem in an R-way branching program model, extending an old counting argument due to Borodin and Cook, but with a new twist involving negatively associated random variables. All our lower bounds hold for both deterministic and randomized algorithms. We view these results as preliminary steps towards understanding the complexity of finding good matchings in graphs in space-limited settings. This is joint work with Yining Chen (Dartmouth).