Games, strategies, and computational complexity

Mathematical Conversations
Topic:Games, strategies, and computational complexity
Speaker:Avi Wigderson
Affiliation:Herbert H. Maass Professor, School of Mathematics
Date:Wednesday, February 12
Time/Room:6:00pm - 7:00pm/Dilworth Room

The following questions are quite intimately related. Please consider them before the talk. Some have surprising answers which are highly nontrivial theorems in computational complexity.

-Do you find Tic-Tac-Toe an interesting game? Why?
-Do you find Chess & Go interesting? Why?
-Is random play (choosing at random from all possible legal moves) a useful strategy in any interesting game? Can it be optimal?

Now assume that White has a winning strategy in Chess, and that you know it.

-Would you still enjoy playing?
-Do you think it is possible to convince a skeptic, beyond a reasonable doubt (and in reasonable time), that you indeed possess such a strategy?

About Mathematical Conversations: We meet in Harry's Bar at 6pm, where free drinks are provided. After 20 minutes, we move to the Dilworth room, where the speaker gives a 20-minute talk, followed by 15 minutes of discussion with the audience. After that we return to the bar for further discussions. Website: http://www.math.ias.edu/~nicks/conversations.html