Name
Abstract | ||
|---|---|---|
A recent result of Moshkovitz \cite{Moshkovitz14} 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 in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel repetition. In this paper, we provide a fix by using a stronger graph that we call fortifiers. Fortifiers are graphs that have both $\ell_1$ and $\ell_2$ 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 (the latter is also the construction used in an independent update \cite{Moshkovitz15} of \cite{Moshkovitz14} with an alternate argument), is a good fortifier. We also show that using a fortifier (in particular $\ell_2$ guarantees) is necessary for obtaining the robustness required for fortification. |
Year | Venue | Field |
|---|---|---|
2015 | APPROX-RANDOM | Graph,Elementary proof,Algorithm,Robustness (computer science),Extractor,Spectral gap,Mathematics |
DocType | Citations | PageRank |
Conference | 3 | 0.40 |
References | Authors | |
10 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amey Bhangale | 1 | 10 | 6.71 |
| Ramprasad Saptharishi | 2 | 184 | 13.72 |
| Girish Varma | 3 | 5 | 2.13 |
| rakesh venkat | 4 | 3 | 2.77 |