Papers by Dana Moshkovitz




Gil Goldshlager, Dana Moshkovitz

Approximating kCSP For Large Alphabet,

Pasin Manurangsi, Dana Moshkovitz

Approximating Dense Max 2-CSPs,

Dana Moshkovitz,

Direct Product Testing With Nearly Identical Sets,

ECCC TR14-182

Subhash Khot, Dana Moshkovitz,

Candidate Lasserre Integrality Gap For Unique Games,

ECCC TR14-142

Dana Moshkovitz,

Parallel Repetition From Fortification,

The proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS14)

The latest version includes an extremely simple proof of parallel repetition and a correction to the fortification lemma.


ECCC TR14-054

Dana Moshkovitz,

Low Degree Test With Polynomially Small Error,


(Previous version “An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing”,

ECCC TR14-30)

Sarah Eisenstat, Dana Moshkovitz, Robert E. Tarjan, Siyao Xu,

Minimum Spanning Tree in Deterministic Linear Time For Graphs of High Girth,


Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz,

AM with Multiple Merlins,

Computational Complexity Conference (CCC14)

ECCC TR14-012

Pasin Manurangsi, Dana Moshkovitz,

Improved Approximation Algorithms for Projection Games,

ArXiv 1408.4048 (full version)

The Proceedings of the 21st European Symposium on Algorithms (ESA13)

Vitaly Abdrashitov, Muriel Médard, Dana Moshkovitz,

Matched Filter Decoding of Random Binary and Gaussian Codes in Broadband Gaussian Channel,

IEEE International Symposium on Information Theory (ISIT13)

Dana Moshkovitz,

The Projection Games Conjecture and the NP-Hardness of lnn-Approximating Set-Cover,

APPROX-RANDOM, 276-287, 2012

ECCC TR11-112

[draft journal version]

Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, Omri Weinstein,

Inapproximability of Densest k-Subgraph From Average Case Hardness,


Subhash Khot, Dana Moshkovitz
NP-Hardness of Approximately Solving Linear Equations Over Reals,

SIAM Journal on Computing, 42(3), 752–791, 2013
The Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC11)

ECCC TR10-112

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)
[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]





Dana Moshkovitz,
Algebraic Construction of Projection PCPs
SIGACT Complexity Column 2012.

Dana Moshkovitz,

The Tale of the PCP Theorem (popular article),