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?

-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?