|
|
|
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) |
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. |
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”, |
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) |
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, |
Dana Moshkovitz, The Projection
Games Conjecture and the NP-Hardness of lnn-Approximating Set-Cover, |
Noga Alon,
Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz,
Omri Weinstein, Inapproximability
of Densest k-Subgraph From Average Case Hardness, Manuscript |
Subhash Khot, Dana Moshkovitz SIAM Journal on
Computing, 42(3), 752–791, 2013 ECCC TR10-112 A previous version achieving hardness
under the Unique Games Conjecture: ECCC TR10-053 |
Dana Moshkovitz, |
Dana Moshkovitz, Ran Raz |
Dana Moshkovitz, Ran Raz |
Dana Moshkovitz, Ran Raz |
Adi Akavia,
Oded Goldreich, Shafi Goldwasser, Dana
Moshkovitz |
Noga Alon, |
Surveys:
Dana Moshkovitz, |
Dana Moshkovitz, The Tale of the PCP Theorem (popular article), ACM XRDS 2012 |