Title: On Fortification of Projection Games
Speaker: Amey Bhangale, Rutgers University
Date: Wednesday, November 18, 2015 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk, we will discuss yet another simplified proof of the Parallel Repetition Theorem for certain games.
A recent result of Moshkovitz presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used there to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove the parallel repetition theorem.
We provide a fix by using a stronger graph that we call fortifiers. Fortifiers are graphs that have both l1 and l2 guarantees on induced distributions from large subsets. We then show that an expander with sufficient spectral gap, or a bi-regular extractor with stronger parameters is a good fortifier. We also show that using a fortifier (in particular l2 guarantees) is necessary for obtaining the robustness required for fortification.
This talk is based on a joint work with Ramprasad Saptharish, Girish Varma and Rakesh Venkat.
See: https://dragon.rutgers.edu/~mk1029/theoryseminarF15.html