4 citations · 7 across the 6 of their papers we have counts for
5 papers · 1 filter
Strong Parallel Repetition for Unique Games on Small Set Expanders
Dana Moshkovitz
Strong Parallel Repetition for Unique Games on Small Set Expanders The strong parallel repetition problem for unique games is to efficiently reduce the 1-delta vs. 1-C*delta gap pr…
Reduction From Non-Unique Games To Boolean Unique Games
Ronen Eldan, Dana Moshkovitz
We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap 1-delta vs. 1-C*delta, for any C> 1, and sufficiently small delta>0) to the problem of proving a PCP…
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian
Dana Moshkovitz, Govind Ramnarayan, Henry Yuen
In this work we show a barrier towards proving a randomness-efficient parallel repetition, a promising avenue for achieving many tight inapproximability results. Feige and Kilian (…
AM with Multiple Merlins
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that ea…
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
Prahladh Harsha, Moses Charikar, Matthew Andrews +14
These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-2…