4 citations · 7 across the 6 of their papers we have counts for
9 papers
Near-Optimal Cayley Expanders for Abelian Groups
Akhil Jalan, Dana Moshkovitz
We give an efficient deterministic algorithm that outputs an expanding generating set for any finite abelian group. The size of the generating set is close to the randomized constr…
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 (…
Amplification and Derandomization Without Slowdown
Ofer Grossman, Dana Moshkovitz
We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most…
Approximating Dense Max 2-CSPs
Pasin Manurangsi, Dana Moshkovitz
In this paper, we present a polynomial-time algorithm that approximates sufficiently high-value Max 2-CSPs on sufficiently dense graphs to within approximation…
Improved Approximation Algorithms for Projection Games
Pasin Manurangsi, Dana Moshkovitz
The projection games (aka Label-Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today…
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…