Dana Moshkovitz

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 34

Top Topics

Space Efficient

Approximation Algorithms

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Joshua Cook, Dana Moshkovitz
Explicit Time and Space Efficient Encoders Exist Only With Random Access. Electron. Colloquium Comput. Complex. (2024)
Joshua Cook, Dana Moshkovitz
Explicit Time and Space Efficient Encoders Exist Only with Random Access. CCC (2024)
Joshua Cook, Dana Moshkovitz
Time and Space Efficient Deterministic Decoders. Electron. Colloquium Comput. Complex. (2024)
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
Almost Chor-Goldreich Sources and Adversarial Random Walks. STOC (2023)
Shuichi Hirahara, Dana Moshkovitz
Regularization of Low Error PCPs and an Application to MCSP. ISAAC (2023)
Geoffrey Mon, Dana Moshkovitz, Justin Oh
Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate. Electron. Colloquium Comput. Complex. (2023)
Joshua Cook, Dana Moshkovitz
Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE. APPROX/RANDOM (2023)
Joshua Cook, Dana Moshkovitz
Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE. Electron. Colloquium Comput. Complex. 29 (2022)
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
Almost Chor-Goldreich Sources and Adversarial Random Walks. Electron. Colloquium Comput. Complex. (2022)
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
Nearly Optimal Pseudorandomness from Hardness. J. ACM 69 (6) (2022)
Ronen Eldan, Dana Moshkovitz
Reduction from Non-Unique Games to Boolean Unique Games. ITCS (2022)
Dana Moshkovitz
Strong Parallel Repetition for Unique Games on Small Set Expanders. CoRR (2021)
Akhil Jalan, Dana Moshkovitz
Near-Optimal Cayley Expanders for Abelian Groups. CoRR (2021)
Akhil Jalan, Dana Moshkovitz
Near-Optimal Cayley Expanders for Abelian Groups. FSTTCS (2021)
Dana Moshkovitz
Strong Parallel Repetition for Unique Games on Small Set Expanders. Electron. Colloquium Comput. Complex. 28 (2021)
Ofer Grossman, Dana Moshkovitz
Amplification and Derandomization without Slowdown. SIAM J. Comput. 49 (5) (2020)
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
Nearly Optimal Pseudorandomness From Hardness. FOCS (2020)
Ronen Eldan, Dana Moshkovitz
Reduction From Non-Unique Games To Boolean Unique Games. CoRR (2020)
Dana Moshkovitz, Justin Oh, David Zuckerman
Randomness Efficient Noise Stability and Generalized Small Bias Sets. FSTTCS (2020)
Ronen Eldan, Dana Moshkovitz
Reduction From Non-Unique Games To Boolean Unique Games. Electron. Colloquium Comput. Complex. 27 (2020)
Dana Moshkovitz
Sliding Scale Conjectures in PCP. SIGACT News 50 (3) (2019)
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
Nearly Optimal Pseudorandomness From Hardness. Electron. Colloquium Comput. Complex. 26 (2019)
Dana Moshkovitz, Michal Moshkovitz
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. ITCS (2018)
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra
Small Set Expansion in The Johnson Graph. Electron. Colloquium Comput. Complex. 25 (2018)
Pasin Manurangsi, Dana Moshkovitz
Improved Approximation Algorithms for Projection Games. Algorithmica 77 (2) (2017)
Michal Moshkovitz, Dana Moshkovitz
Mixing Implies Lower Bounds for Space Bounded Learning. Electron. Colloquium Comput. Complex. 24 (2017)
Michal Moshkovitz, Dana Moshkovitz
Mixing Implies Strong Lower Bounds for Space Bounded Learning. Electron. Colloquium Comput. Complex. 24 (2017)
Dana Moshkovitz
Low-degree test with polynomially small error. Comput. Complex. 26 (3) (2017)
Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan
Approximation Algorithms for Label Cover and The Log-Density Threshold. SODA (2017)
Dana Moshkovitz, Michal Moshkovitz
Mixing Implies Lower Bounds for Space Bounded Learning. COLT (2017)
Ofer Grossman, Dana Moshkovitz
Amplification and Derandomization without Slowdown. FOCS (2016)
Dana Moshkovitz, Govind Ramnarayan, Henry Yuen
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. APPROX-RANDOM (2016)
Subhash Khot, Dana Moshkovitz
Candidate hard unique game. STOC (2016)
Dana Moshkovitz, Govind Ramnarayan, Henry Yuen
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. CoRR (2016)
Dana Moshkovitz
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. Theory Comput. 11 (2015)
Pasin Manurangsi, Dana Moshkovitz
Approximating Dense Max 2-CSPs. CoRR (2015)
Ofer Grossman, Dana Moshkovitz
Amplification and Derandomization Without Slowdown. CoRR (2015)
Pasin Manurangsi, Dana Moshkovitz
Approximating Dense Max 2-CSPs. APPROX-RANDOM (2015)
Ofer Grossman, Dana Moshkovitz
Amplification and Derandomization Without Slowdown. Electron. Colloquium Comput. Complex. 22 (2015)
Dana Moshkovitz
Parallel Repetition from Fortification. FOCS (2014)
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
AM with Multiple Merlins. Electron. Colloquium Comput. Complex. 21 (2014)
Dana Moshkovitz
An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing. Electron. Colloquium Comput. Complex. 21 (2014)
Dana Moshkovitz
Parallel Repetition of Fortified Games. Electron. Colloquium Comput. Complex. 21 (2014)
Pasin Manurangsi, Dana Moshkovitz
Improved Approximation Algorithms for Projection Games. CoRR (2014)
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
AM with Multiple Merlins. Computational Complexity Conference (2014)
Dana Moshkovitz
Direct Product Testing With Nearly Identical Sets. Electron. Colloquium Comput. Complex. 21 (2014)
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
AM with Multiple Merlins. CoRR (2014)
Subhash Khot, Dana Moshkovitz
Candidate Lasserre Integrality Gap For Unique Games. Electron. Colloquium Comput. Complex. 21 (2014)
Pasin Manurangsi, Dana Moshkovitz
Improved Approximation Algorithms for Projection Games - (Extended Abstract). ESA (2013)
Subhash Khot, Dana Moshkovitz
-Hardness of Approximately Solving Linear Equations over Reals. SIAM J. Comput. 42 (3) (2013)
Vitaly Abdrashitov, Muriel Médard, Dana Moshkovitz
Matched filter decoding of random binary and Gaussian codes in broadband Gaussian channel. ISIT (2013)
Dana Moshkovitz
The tale of the PCP theorem. XRDS 18 (3) (2012)
Dana Moshkovitz
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. APPROX-RANDOM (2012)
Dana Moshkovitz
Guest column: algebraic construction of projection PCPs. SIGACT News 43 (1) (2012)
Subhash Khot, Dana Moshkovitz
NP-hardness of approximately solving linear equations over reals. STOC (2011)
Dana Moshkovitz
The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover. Electron. Colloquium Comput. Complex. 18 (2011)
Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz
Erratum for: on basing one-way functions on NP-hardness. STOC (2010)
Dana Moshkovitz
An Alternative Proof of The Schwartz-Zippel Lemma. Electron. Colloquium Comput. Complex. 17 (2010)
Subhash Khot, Dana Moshkovitz
NP-Hardness of Approximately Solving Linear Equations Over Reals. Electron. Colloquium Comput. Complex. 17 (2010)
Dana Moshkovitz, Subhash Khot
Hardness of Approximately Solving Linear Equations Over Reals. Electron. Colloquium Comput. Complex. 17 (2010)
Dana Moshkovitz, Ran Raz
Two-query PCP with subconstant error. J. ACM 57 (5) (2010)
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
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) CoRR (2010)
Dana Moshkovitz, Ran Raz
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size. Comput. Complex. 19 (3) (2010)
Dana Moshkovitz, Ran Raz
Two Query PCP with Sub-Constant Error. Electron. Colloquium Comput. Complex. 15 (071) (2008)
Dana Moshkovitz, Ran Raz
Two Query PCP with Sub-Constant Error. FOCS (2008)
Dana Moshkovitz, Ran Raz
Sub-Constant Error Low Degree Test of Almost-Linear Size. SIAM J. Comput. 38 (1) (2008)
Dana Moshkovitz, Ran Raz
Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size. Electron. Colloquium Comput. Complex. 14 (026) (2007)
Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz
On basing one-way functions on NP-hardness. STOC (2006)
Dana Moshkovitz, Ran Raz
Sub-constant error low degree test of almost-linear size. STOC (2006)
Noga Alon, Dana Moshkovitz, Shmuel Safra
-restrictions. ACM Trans. Algorithms 2 (2) (2006)
Dana Moshkovitz, Ran Raz
Sub-Constant Error Low Degree Test of Almost Linear Size Electron. Colloquium Comput. Complex. (086) (2005)