Abstract

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.

Attachment

Video Recording