Talks
Spring 2015
Small Value Parallel Repetition for General Games
Monday, April 20th, 2015, 11:45 am–12:15 pm
Speaker:
Location:
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.
Attachment | Size |
---|---|
gargslides.pptx | 1.21 MB |