Dana Moshkovitz

According to our database, Dana Moshkovitz authored at least 48 papers between 2006 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2025

Time and Space Efficient Deterministic Decoders.

Joshua Cook, Dana Moshkovitz

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Online Condensing of Unpredictable Sources via Random Walks.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate.

Geoffrey Mon, Dana Moshkovitz, Justin Oh

Proceedings of the IEEE International Symposium on Information Theory, 2024

Explicit Time and Space Efficient Encoders Exist Only with Random Access.

Joshua Cook, Dana Moshkovitz

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Almost Chor-Goldreich Sources and Adversarial Random Walks.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Regularization of Low Error PCPs and an Application to MCSP.

Shuichi Hirahara, Dana Moshkovitz

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE.

Joshua Cook, Dana Moshkovitz

Proceedings of the Approximation, 2023

2022

Reduction from Non-Unique Games to Boolean Unique Games.

Ronen Eldan, Dana Moshkovitz

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Strong Parallel Repetition for Unique Games on Small Set Expanders.

Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2021

Near-Optimal Cayley Expanders for Abelian Groups.

Akhil Jalan, Dana Moshkovitz

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

Randomness Efficient Noise Stability and Generalized Small Bias Sets.

Dana Moshkovitz, Justin Oh, David Zuckerman

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Nearly Optimal Pseudorandomness From Hardness.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Sliding Scale Conjectures in PCP.

Dana Moshkovitz

SIGACT News, 2019

Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019).

Dana Moshkovitz, Sushant Sachdeva

SIAM J. Comput., 2019

2018

Small Set Expansion in The Johnson Graph.

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

Electron. Colloquium Comput. Complex., 2018

Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning.

Dana Moshkovitz, Michal Moshkovitz

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Mixing Implies Strong Lower Bounds for Space Bounded Learning.

Michal Moshkovitz, Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2017

Low-degree test with polynomially small error.

Dana Moshkovitz

Comput. Complex., 2017

Improved Approximation Algorithms for Projection Games.

Pasin Manurangsi, Dana Moshkovitz

Algorithmica, 2017

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

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

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Mixing Implies Lower Bounds for Space Bounded Learning.

Dana Moshkovitz, Michal Moshkovitz

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Candidate hard unique game.

Subhash Khot, Dana Moshkovitz

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Amplification and Derandomization without Slowdown.

Ofer Grossman, Dana Moshkovitz

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

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

Dana Moshkovitz, Govind Ramnarayan, Henry Yuen

Proceedings of the Approximation, 2016

2015

Approximating Dense Max 2-CSPs.

Pasin Manurangsi, Dana Moshkovitz

Proceedings of the Approximation, 2015

2014

Direct Product Testing With Nearly Identical Sets.

Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2014

Parallel Repetition of Fortified Games.

Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2014

An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing.

Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2014

Candidate Lasserre Integrality Gap For Unique Games.

Subhash Khot, Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2014

Parallel Repetition from Fortification.

Dana Moshkovitz

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

AM with Multiple Merlins.

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

<i>NP</i>-Hardness of Approximately Solving Linear Equations over Reals.

Subhash Khot, Dana Moshkovitz

SIAM J. Comput., 2013

Matched filter decoding of random binary and Gaussian codes in broadband Gaussian channel.

Vitaly Abdrashitov, Muriel Médard, Dana Moshkovitz

Proceedings of the 2013 IEEE International Symposium on Information Theory, 2013

Improved Approximation Algorithms for Projection Games - (Extended Abstract).

Pasin Manurangsi, Dana Moshkovitz

Proceedings of the Algorithms - ESA 2013, 2013

2012

Guest column: algebraic construction of projection PCPs.

Dana Moshkovitz

SIGACT News, 2012

The tale of the PCP theorem.

Dana Moshkovitz

XRDS, 2012

The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover.

Dana Moshkovitz

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

NP-hardness of approximately solving linear equations over reals.

Subhash Khot, Dana Moshkovitz

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Two-query PCP with subconstant error.

Dana Moshkovitz, Ran Raz

J. ACM, 2010

Hardness of Approximately Solving Linear Equations Over Reals.

Dana Moshkovitz, Subhash Khot

Electron. Colloquium Comput. Complex., 2010

An Alternative Proof of The Schwartz-Zippel Lemma.

Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer

CoRR, 2010

Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size.

Dana Moshkovitz, Ran Raz

Comput. Complex., 2010

Erratum for: on basing one-way functions on NP-hardness.

Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2008

Two Query PCP with Sub-Constant Error.

Dana Moshkovitz, Ran Raz

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2006

Algorithmic construction of sets for <i>k</i>-restrictions.

Noga Alon, Dana Moshkovitz, Shmuel Safra

ACM Trans. Algorithms, 2006

Sub-constant error low degree test of almost-linear size.

Dana Moshkovitz, Ran Raz

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

On basing one-way functions on NP-hardness.

Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006