Thesis Defense: Mohammad Bavarian "Parallel Repetition of Multi-party and Quantum Games via Anchoring and Fortification"

Speaker: Mohammad Bavarian , MIT

Date: Thursday, May 04, 2017

Time: 4:00 PM to 5:00 PM

Refreshments: 3:45 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Madhu Sudan and Peter Shor, Harvard and MIT

Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Joanne Talbot Hanley at Wednesday, April 26, 2017 at 5:15 PM.