Dana Moshkovitz

77 papers A* 13A 8B 3Journal 48Unranked 5

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