Papers by Dana Moshkovitz

 

 

     

Eden Chlamtáč, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan,

Approximation Algorithms for Label Cover and The Log-Density Threshold,

Submitted

Subhash Khot, Dana Moshkovitz,

Candidate Hard Unique Game,

The proceedings of the 48th Annual Symposium on the Theory of Computing (STOC16)

Preliminary version without analysis: ECCC TR14-142

Lemma in the proof: Direct Product Testing With Nearly Identical Sets, ECCC TR14-182

[paper]

Ofer Grossman, Dana Moshkovitz,

Amplification and Derandomization Without Slowdown,

The proceedings of the 57th Annual IEEE  Symposium  on Foundations of Computer Science (FOCS16)

ECCC TR15-158/ArXiv:1509.08123

[paper][presentation]

Dana Moshkovitz, Govind Ramnarayan, Henry Yuen,

A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian,

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM16)

[paper]

Gil Goldshlager, Dana Moshkovitz

Approximating kCSP For Large Alphabet,

[paper]

Pasin Manurangsi, Dana Moshkovitz

Approximating Dense Max 2-CSPs,

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX15)

[paper]

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.

[paper][presentation]

ECCC TR14-054

Dana Moshkovitz,

Low Degree Test With Polynomially Small Error,

[paper]

To appear in the journal Computational Complexity

(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,

[paper]

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,

Algorithmica, 2015

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,

Theory of Computing APPROX-RANDOM 2012 Special Issue

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,

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

 

 

Surveys:

 

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

Dana Moshkovitz,

The Tale of the PCP Theorem (popular article),

ACM XRDS 2012