Thesis Defense: Mohammad Bavarian "Parallel Repetition of Multi-party and Quantum Games via Anchoring and Fortification"
Date: Thursday, May 04, 2017
Time: 4:00 PM to 5:00 PM
Refreshments: 3:45 PM
Host: Madhu Sudan and Peter Shor, Harvard and MIT
Contact: Joanne Talbot Hanley, 617-253-6054, firstname.lastname@example.org
Speaker URL: None
TALK: Thesis Defense: Mohammad Bavarian "Parallel Repetition of Multi-party and Quantum Games via Anchoring and Fortification"
Abstract: Parallel repetition is a natural operation for amplifying the hardness inherent in multiplayer games. Despite being very simple to define, it has been known since the 90's that the behavior of this operation is subtle. For example, even though an exponential decay of the value of games under parallel repetition can be suspected from the definition, the exact nature of behavior as understood by the relevant counter-examples reveal various intriguing properties and surprises.
Through the work of many theoretical computer scientists over two decades (e.g. Feige, Kilian, Raz, Holenstein, Rao, etc.) the behavior of parallel repetition of two-player classical games came to be well-understood. But until very recently, no similar hardness amplification results were known for multiplayer (in games with more than two players) and quantum games. This thesis focuses on these two problems and resolves some of the most important challenges regarding the parallel repetition of multiplayer and quantum games. Drawing from the works of Feige-Kilian and Moshkovitz, we introduce operations of anchoring and fortification which are central to our approach to obtaining exponential hardness amplification in our general setting. We show how these simple operations enable us to circumvent some of the major difficulties in obtaining strong parallel repetition results for games with three (or more) players and quantum games.
Created by Joanne Talbot Hanley at Wednesday, April 26, 2017 at 5:15 PM.