activity
20102021
most citedLimits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

4 citations · 7 across the 6 of their papers we have counts for

collaborators
Showing 2020Show all

1 paper · 1 filter

cs.CC2020

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…