|
|
|
|
|
|
Subhash Khot, Dor Minzer, Dana Moshkovitz, Shmuel Safra Small Set Expansion in The Johnson Graph, |
|
Dana Moshkovitz, Michal Moshkovitz Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning, The proceedings of the 9th Innovations in
Theoretical Computer Science conference (ITCS18) |
|
Dana Moshkovitz, Michal Moshkovitz Mixing Implies Lower Bounds For
Space Bounded Learning, The
proceedings of the 30th Annual Conference on Learning Theory (COLT17)
|
|
Eden Chlamtáč, Pasin
Manurangsi, Dana Moshkovitz,
Aravindan Vijayaraghavan Approximation Algorithms for Label Cover and The
Log-Density Threshold, The
proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA17) |
|
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] Computational
Complexity journal, 2016 (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 |