DIMACS Princeton Theory Seminar


Making Games Short


Joe Kilian
NEC Research


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:05 PM (Lunch will be served at 11:45 AM)
Thursday, March 27, 1997


Sanjeev Arora (arora@cs.princeton.edu)


We study the complexity of refereed games, in which two computationally unlimited players play against each other, and a polynomial time referee monitors the game and announces the winner. The players may exchange messages with the referee in private, resulting in a game of perfect recall but incomplete information. We show that any EXPTIME statement can be efficiently transformed into a refereed game in which if the statement is true, the first player wins with overwhelming probability, and if the statement is false, the second player wins with overwhelming probability. %This result is best possible, and answers an open question of %Feige, Shamir and Tennenholtz, and of Feigenbaum, Koller and Shor. We also prove matching PSPACE upper and lower bounds on the complexity of statements that have refereed games that take one round of communication.

(Joint work with Uri Feige)

Document last modified on March 21, 1997