### DIMACS Theoretical Computer Science Seminar

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