|
Dana Moshkovitz,
The Projection Games Conjecture
and the NP-Hardness of lnn-Approximating
Set-Cover,
APPROX-RANDOM,
276-287, 2012
ECCC TR11-112
|
|
Noga Alon, Sanjeev Arora, Rajsekar
Manokaran, Dana Moshkovitz,
Omri Weinstein,
Inapproximability of Densest k-Subgraph
From Average Case Hardness,
Manuscript
|
|
Subhash Khot, Dana Moshkovitz
NP-Hardness
of Approximately Solving Linear Equations Over Reals,
The Proceedings of the 43rd
annual ACM symposium on Theory of computing (STOC11)
ECCC TR10-112
[paper][presentation]
A previous version achieving
hardness under the Unique Games Conjecture: ECCC TR10-053
|
|
Dana Moshkovitz,
An Alternative Proof of The Schwartz-Zippel Lemma,
ECCC TR10-096
|
|
Dana Moshkovitz, Ran Raz
Two Query PCP with Sub-Constant Error, Overview
FOCS08 Best Paper award
The
Journal of the ACM, 57(5),
2010
The
Proceedings of The 49th Annual IEEE Symposium on Foundations of Computer
Science (FOCS08)
ECCC
TR08-071
|
|
Dana Moshkovitz, Ran Raz
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size,
The Journal
Computational Complexity, 19(3):367-422, 2010.
ECCC
TR07-026
[full version] [IMU07
Presentation]
|
|
Dana Moshkovitz, Ran Raz
Sub-Constant Error Low Degree Test of Almost-Linear Size,
SIAM
Journal on Computing, 38(1):140-180, 2008
The
Proceedings of The 38th ACM Symposium on Theory of Computing (STOC06)
ECCC
TR05-086
[conference
version][full version] [STOC06 presentation] [IMU07 Presentation]
|
|
Adi Akavia, Oded
Goldreich, Shafi Goldwasser, Dana Moshkovitz
On Basing One-Way Functions on NP-Hardness,
The Proceedings
of The 38th ACM Symposium on Theory of Computing (STOC06)
Erratum
[conference
version]
|
|
Noga Alon, Dana
Moshkovitz, Shmuel Safra
Algorithmic Construction of Sets for k-Restrictions, Overview
The
ACM Transactions on Algorithms, 2(2):153-177, 2006
[full
version] [presentation]
|