DIMACS Princeton Theory Seminar

Title:

Making Games Short

Speaker:

Joe Kilian

NEC Research

Place:

Room 402, Computer Science Building

35 Olden Street

Princeton University.

Time:

12:05 PM (Lunch will be served at 11:45 AM)

Thursday, March 27, 1997

Contact:

Sanjeev Arora (arora@cs.princeton.edu)

Abstract:

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