Title: A Parallel Search Game related to Data Structure Lower Bounds
Speaker: Navin Goyal, Rutgers University
Date: February 23, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider a parallel search game, a simple special case of which is the following and constitutes a nice puzzle, which the reader may want to think about.
We have a boxes labeled 0, ..., a-1, and a pieces of paper labeled 0, ..., a-1. The game is played between player I and a team consisting of a players II_0, ..., II_{a-1}. Player I secretly colors each slip red or blue, and puts each piece of paper in a box without the team watching. Now for i \in {0, ..., a-1} player II_i can look in at most a/2 boxes using any adaptive strategy and based on this must make a guess about the color of the slip labeled i. This is done by each of the player on the team without communication or observation between them. The team wins if every player in the team correctly announces the color of his slip. Suppose player I adopts the strategy of coloring each slip of paper uniformly at random and independently putting them at random into the boxes so that each box gets exactly one slip. The question is with what probability can the team win.
The game that we consider is more complicated. It arose in the work of Gal and Miltersen on space-time trade-offs for data structures for pattern matching. I'll explain this connection and then show a good strategy for the team in the search game.
This is joint work with Mike Saks.
See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html