Spring 2015

Small Value Parallel Repetition for General Games

Monday, Apr. 20, 2015 11:45 am12:15 pm

Add to Calendar


Calvin Lab Auditorium

We prove a parallel repetition theorem for general games with value tending to 0. We also give alternate proofs for the parallel repetition theorems of Dinur & Steurer, Holenstein and Rao. Parallel repetition theorems fall in the category of hardness amplification results and have a lot of applications in theoretical computer science, including hardness of approximation. Our proofs heavily rely on information theory but only use basic properties of mutual information such as chain rule. I will give a high level overview of our proof focussing on the role of information theory. This is joint work with Mark Braverman.

File gargslides.pptx1.21 MB