Zobrazeno 1 - 10
of 59
pro vyhledávání: '"MOSHKOVITZ, DANA"'
Autor:
Jalan, Akhil, Moshkovitz, Dana
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 construction of Alon and Roichman (1994), improving upon various determinist
Externí odkaz:
http://arxiv.org/abs/2105.01149
Autor:
Moshkovitz, Dana
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 problem of Boolean unique games (where C>1 is a sufficiently large const
Externí odkaz:
http://arxiv.org/abs/2103.08743
Autor:
DORON, DEAN1 deand@bgu.ac.il, MOSHKOVITZ, DANA2 diz@utexas.edu, OH, JUSTIN2, ZUCKERMAN, DAVID2
Publikováno v:
Journal of the ACM. Nov2022, Vol. 69 Issue 6, p1-55. 55p.
Autor:
Eldan, Ronen, Moshkovitz, Dana
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 Theorem for a certain non-unique game. In a previous work, Khot and Mo
Externí odkaz:
http://arxiv.org/abs/2006.13073
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 (STOC'95) proved an impossibility result for randomness-efficient paral
Externí odkaz:
http://arxiv.org/abs/1607.07130
Autor:
Grossman, Ofer, Moshkovitz, Dana
We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorith
Externí odkaz:
http://arxiv.org/abs/1509.08123
Autor:
Manurangsi, Pasin, Moshkovitz, Dana
In this paper, we present a polynomial-time algorithm that approximates sufficiently high-value Max 2-CSPs on sufficiently dense graphs to within $O(N^{\varepsilon})$ approximation ratio for any constant $\varepsilon > 0$. Using this algorithm, we al
Externí odkaz:
http://arxiv.org/abs/1507.08348
Autor:
Manurangsi, Pasin, Moshkovitz, Dana
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 are reductions from Label-Cover. In this paper we design several appr
Externí odkaz:
http://arxiv.org/abs/1408.4048
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 each Merlin receives an independent random challenge from Arthur. One mo
Externí odkaz:
http://arxiv.org/abs/1401.6848
Autor:
Harsha, Prahladh, Charikar, Moses, Andrews, Matthew, Arora, Sanjeev, Khot, Subhash, Moshkovitz, Dana, Zhang, Lisa, Aazami, Ashkan, Desai, Dev, Gorodezky, Igor, Jagannathan, Geetha, Kulikov, Alexander S., Mir, Darakhshan J., Newman, Alantha, Nikolov, Aleksandar, Pritchard, David, Spencer, Gwen
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-21 July, 2009. This tutorial was jointly sponsored by the DIMACS Specia
Externí odkaz:
http://arxiv.org/abs/1002.3864