Dana Moshkovitz

Most-cited papers

Algorithmic construction of sets for k-restrictions
N. Alon, Dana Moshkovitz, S. Safra
2006TALG315 citations
Semantic Scholar
Two Query PCP with Sub-Constant Error
Dana Moshkovitz, R. Raz
20082008 49th Annual IEEE Symposium on Foundations of Computer Science233 citations
Semantic Scholar
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
Dana Moshkovitz
2012Theory of Computing173 citations Open access
Semantic Scholar
On basing one-way functions on NP-hardness
Adi Akavia, O. Goldreich, S. Goldwasser, Dana Moshkovitz
2006Symposium on the Theory of Computing108 citations
Semantic Scholar
Inapproximabilty of Densest κ-Subgraph from Average Case Hardness
N. Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz +1 more
201185 citations
Semantic Scholar
AM with Multiple Merlins
S. Aaronson, R. Impagliazzo, Dana Moshkovitz
2014Cybersecurity and Cyberforensics Conference69 citations
Semantic Scholar
Sub-constant error low degree test of almost-linear size
Dana Moshkovitz, R. Raz
2006Symposium on the Theory of Computing61 citations Open access
Semantic Scholar
Mixing Implies Lower Bounds for Space Bounded Learning
Dana Moshkovitz, Michal Moshkovitz
2017Annual Conference Computational Learning Theory42 citations
Semantic Scholar
Nearly Optimal Pseudorandomness From Hardness
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
2020IEEE Annual Symposium on Foundations of Computer Science39 citations
Semantic Scholar
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning
Dana Moshkovitz, Michal Moshkovitz
2018Information Technology Convergence and Services31 citations
Semantic Scholar
Parallel Repetition from Fortification
Dana Moshkovitz
2014IEEE Annual Symposium on Foundations of Computer Science30 citations Open access
Semantic Scholar
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size
Dana Moshkovitz, R. Raz
2010Computational Complexity27 citations Open access
Semantic Scholar
Small Set Expansion in The Johnson Graph
Subhash Khot, Dor Minzer, Dana Moshkovitz, S. Safra
2018Electron. Colloquium Comput. Complex.26 citations
Semantic Scholar
Approximation Algorithms for Label Cover and The Log-Density Threshold
E. Chlamtáč, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan
2017ACM-SIAM Symposium on Discrete Algorithms22 citations Open access
Semantic Scholar
Candidate hard unique game
Subhash Khot, Dana Moshkovitz
2016Symposium on the Theory of Computing22 citations
Semantic Scholar
An Alternative Proof of The Schwartz-Zippel Lemma
Dana Moshkovitz
2010Electron. Colloquium Comput. Complex.19 citations
Semantic Scholar
NP-hardness of approximately solving linear equations over reals
Subhash Khot, Dana Moshkovitz
2011SIAM journal on computing (Print)18 citations Open access
Semantic Scholar
Approximating Dense Max 2-CSPs
Pasin Manurangsi, Dana Moshkovitz
2015International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques15 citations
Semantic Scholar
Near-Optimal Cayley Expanders for Abelian Groups
Akhil Jalan, Dana Moshkovitz
2021Foundations of Software Technology and Theoretical Computer Science13 citations
Semantic Scholar
Improved Approximation Algorithms for Projection Games
Pasin Manurangsi, Dana Moshkovitz
2013Algorithmica12 citations Open access
Semantic Scholar
Erratum for: on basing one-way functions on NP-hardness
Adi Akavia, Oded Goldreich, S. Goldwasser, Dana Moshkovitz
2010Symposium on the Theory of Computing12 citations
Semantic Scholar
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
P. Harsha, M. Charikar, M. Andrews, Sanjeev Arora +13 more
2010arXiv.org12 citations
Semantic Scholar
Algorithmic construction of sets for
N. Alon, Dana Moshkovitz, S. Safra
200611 citations
Semantic Scholar
Amplification and Derandomization without Slowdown
O. Grossman, Dana Moshkovitz
2015IEEE Annual Symposium on Foundations of Computer Science10 citations Open access
Semantic Scholar
Almost Chor-Goldreich Sources and Adversarial Random Walks
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
2023Electron. Colloquium Comput. Complex.8 citations Open access
Semantic Scholar
Low-degree test with polynomially small error
Dana Moshkovitz
2016Computational Complexity8 citations
Semantic Scholar
Mixing Implies Strong Lower Bounds for Space Bounded Learning
Michal Moshkovitz, Dana Moshkovitz
2017Electron. Colloquium Comput. Complex.6 citations
Semantic Scholar
An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing
Dana Moshkovitz
2014Electron. Colloquium Comput. Complex.5 citations
Semantic Scholar
Online Condensing of Unpredictable Sources via Random Walks
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
2024Electron. Colloquium Comput. Complex.4 citations
Semantic Scholar
Parallel Repetition of Fortified Games
Dana Moshkovitz
2014Electron. Colloquium Comput. Complex.4 citations
Semantic Scholar
Explicit Time and Space Efficient Encoders Exist Only With Random Access
Joshua Cook, Dana Moshkovitz
2024Electron. Colloquium Comput. Complex.3 citations
Semantic Scholar
Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE
Joshua Cook, Dana Moshkovitz
2022Electron. Colloquium Comput. Complex.3 citations
Semantic Scholar
Strong Parallel Repetition for Unique Games on Small Set Expanders
Dana Moshkovitz
2021Empirical Software Engineering3 citations
Semantic Scholar
Reduction From Non-Unique Games To Boolean Unique Games
Ronen Eldan, Dana Moshkovitz
2020Electron. Colloquium Comput. Complex.3 citations
Semantic Scholar
Sliding Scale Conjectures in PCP
Dana Moshkovitz
2019Sigact News3 citations
Semantic Scholar
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian
Dana Moshkovitz, Govind Ramnarayan, Henry S. Yuen
2016International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques3 citations
Semantic Scholar
Time and Space Efficient Deterministic Decoders
Joshua Cook, Dana Moshkovitz
2025Electron. Colloquium Comput. Complex.2 citations
Semantic Scholar
Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate
Geoffrey Mon, Dana Moshkovitz, Justin Oh
2024International Symposium on Information Theory2 citations
Semantic Scholar
Approximating kCSP For Large Alphabets
Gil Goldshlager, Dana Moshkovitz
20152 citations
Semantic Scholar
Direct Product Testing With Nearly Identical Sets
Dana Moshkovitz
2014Electron. Colloquium Comput. Complex.2 citations
Semantic Scholar
Matched filter decoding of random binary and Gaussian codes in broadband Gaussian channel
Vitaly Abdrashitov, M. Médard, Dana Moshkovitz
20132013 IEEE International Symposium on Information Theory2 citations Open access
Semantic Scholar
Regularization of Low Error PCPs and an Application to MCSP
Shuichi Hirahara, Dana Moshkovitz
2023International Symposium on Algorithms and Computation1 citations
Semantic Scholar
Randomness Efficient Noise Stability and Generalized Small Bias Sets
Dana Moshkovitz, Justin Oh, David Zuckerman
2020Foundations of Software Technology and Theoretical Computer Science1 citations
Semantic Scholar
Candidate Lasserre Integrality Gap For Unique Games
Subhash Khot, Dana Moshkovitz
2014Electron. Colloquium Comput. Complex.1 citations
Semantic Scholar
Lecture 9 : The PCP Theorem Via gap Amplification
Dana Moshkovitz
20111 citations
Semantic Scholar
Lecture 3 : The Sum Check Protocol
Dana Moshkovitz, Michael S. Forbes
20111 citations
Semantic Scholar
X R D S @bullet S P R I N G 2 0 1 2 @bullet V O L . 1 8 @bullet N O . 3 the Tale of the Pcp Theorem
Dana Moshkovitz
1 citations
Semantic Scholar
Pseudorandomness Beating the Hybrid Argument for Insensitive Algorithms
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
2026Electron. Colloquium Comput. Complex.0 citations
Semantic Scholar
Time and Space Efficient Deterministic List Decoding
Joshua Cook, Dana Moshkovitz
2025Information Technology Convergence and Services0 citations
Semantic Scholar
Small Set Expansion in the Johnson Graph
Subhash Khot, Dor Minzer, Dana Moshkovitz, S. Safra
2025Theory of Computing0 citations Open access
Semantic Scholar