![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Dana Moshkovitz
Person information
- affiliation: University of Texas at Austin, TX, USA
- affiliation (former): Massachusetts Institute of Technology, Cambridge, USA
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c25]Joshua Cook, Dana Moshkovitz:
Explicit Time and Space Efficient Encoders Exist Only with Random Access. CCC 2024: 5:1-5:54 - [i32]Joshua Cook, Dana Moshkovitz:
Explicit Time and Space Efficient Encoders Exist Only With Random Access. Electron. Colloquium Comput. Complex. TR24 (2024) - [i31]Joshua Cook, Dana Moshkovitz:
Time and Space Efficient Deterministic Decoders. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c24]Joshua Cook, Dana Moshkovitz:
Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE. APPROX/RANDOM 2023: 55:1-55:22 - [c23]Shuichi Hirahara, Dana Moshkovitz:
Regularization of Low Error PCPs and an Application to MCSP. ISAAC 2023: 39:1-39:16 - [c22]Dean Doron
, Dana Moshkovitz, Justin Oh, David Zuckerman:
Almost Chor-Goldreich Sources and Adversarial Random Walks. STOC 2023: 1-9 - [i30]Geoffrey Mon, Dana Moshkovitz, Justin Oh:
Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j13]Dean Doron
, Dana Moshkovitz
, Justin Oh
, David Zuckerman
:
Nearly Optimal Pseudorandomness from Hardness. J. ACM 69(6): 43:1-43:55 (2022) - [c21]Ronen Eldan, Dana Moshkovitz:
Reduction from Non-Unique Games to Boolean Unique Games. ITCS 2022: 64:1-64:25 - [i29]Joshua Cook, Dana Moshkovitz:
Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE. Electron. Colloquium Comput. Complex. TR22 (2022) - [i28]Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Almost Chor-Goldreich Sources and Adversarial Random Walks. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c20]Akhil Jalan, Dana Moshkovitz:
Near-Optimal Cayley Expanders for Abelian Groups. FSTTCS 2021: 24:1-24:23 - [i27]Akhil Jalan, Dana Moshkovitz:
Near-Optimal Cayley Expanders for Abelian Groups. CoRR abs/2105.01149 (2021) - [i26]Dana Moshkovitz:
Strong Parallel Repetition for Unique Games on Small Set Expanders. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j12]Ofer Grossman, Dana Moshkovitz:
Amplification and Derandomization without Slowdown. SIAM J. Comput. 49(5): 959-998 (2020) - [c19]Dean Doron
, Dana Moshkovitz, Justin Oh, David Zuckerman:
Nearly Optimal Pseudorandomness From Hardness. FOCS 2020: 1057-1068 - [c18]Dana Moshkovitz, Justin Oh, David Zuckerman:
Randomness Efficient Noise Stability and Generalized Small Bias Sets. FSTTCS 2020: 31:1-31:16 - [i25]Ronen Eldan, Dana Moshkovitz:
Reduction From Non-Unique Games To Boolean Unique Games. CoRR abs/2006.13073 (2020) - [i24]Ronen Eldan, Dana Moshkovitz:
Reduction From Non-Unique Games To Boolean Unique Games. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j11]Dana Moshkovitz:
Sliding Scale Conjectures in PCP. SIGACT News 50(3): 25-33 (2019) - [i23]Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Nearly Optimal Pseudorandomness From Hardness. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c17]Dana Moshkovitz, Michal Moshkovitz:
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. ITCS 2018: 28:1-28:20 - [i22]Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra
:
Small Set Expansion in The Johnson Graph. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j10]Pasin Manurangsi
, Dana Moshkovitz:
Improved Approximation Algorithms for Projection Games. Algorithmica 77(2): 555-594 (2017) - [j9]Dana Moshkovitz:
Low-degree test with polynomially small error. Comput. Complex. 26(3): 531-582 (2017) - [c16]Dana Moshkovitz, Michal Moshkovitz:
Mixing Implies Lower Bounds for Space Bounded Learning. COLT 2017: 1516-1566 - [c15]Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan:
Approximation Algorithms for Label Cover and The Log-Density Threshold. SODA 2017: 900-919 - [i21]Michal Moshkovitz, Dana Moshkovitz:
Mixing Implies Lower Bounds for Space Bounded Learning. Electron. Colloquium Comput. Complex. TR17 (2017) - [i20]Michal Moshkovitz, Dana Moshkovitz:
Mixing Implies Strong Lower Bounds for Space Bounded Learning. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [c14]Dana Moshkovitz, Govind Ramnarayan, Henry Yuen:
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. APPROX-RANDOM 2016: 42:3-42:29 - [c13]Ofer Grossman, Dana Moshkovitz:
Amplification and Derandomization without Slowdown. FOCS 2016: 770-779 - [c12]Subhash Khot, Dana Moshkovitz:
Candidate hard unique game. STOC 2016: 63-76 - [i19]Dana Moshkovitz, Govind Ramnarayan, Henry Yuen:
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. CoRR abs/1607.07130 (2016) - 2015
- [j8]Dana Moshkovitz:
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. Theory Comput. 11: 221-235 (2015) - [c11]Pasin Manurangsi, Dana Moshkovitz:
Approximating Dense Max 2-CSPs. APPROX-RANDOM 2015: 396-415 - [i18]Pasin Manurangsi, Dana Moshkovitz:
Approximating Dense Max 2-CSPs. CoRR abs/1507.08348 (2015) - [i17]Ofer Grossman, Dana Moshkovitz:
Amplification and Derandomization Without Slowdown. CoRR abs/1509.08123 (2015) - [i16]Ofer Grossman, Dana Moshkovitz:
Amplification and Derandomization Without Slowdown. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c10]Scott Aaronson, Russell Impagliazzo
, Dana Moshkovitz:
AM with Multiple Merlins. CCC 2014: 44-55 - [c9]Dana Moshkovitz:
Parallel Repetition from Fortification. FOCS 2014: 414-423 - [i15]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. CoRR abs/1401.6848 (2014) - [i14]Pasin Manurangsi, Dana Moshkovitz:
Improved Approximation Algorithms for Projection Games. CoRR abs/1408.4048 (2014) - [i13]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. Electron. Colloquium Comput. Complex. TR14 (2014) - [i12]Subhash Khot, Dana Moshkovitz:
Candidate Lasserre Integrality Gap For Unique Games. Electron. Colloquium Comput. Complex. TR14 (2014) - [i11]Dana Moshkovitz:
An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing. Electron. Colloquium Comput. Complex. TR14 (2014) - [i10]Dana Moshkovitz:
Parallel Repetition of Fortified Games. Electron. Colloquium Comput. Complex. TR14 (2014) - [i9]Dana Moshkovitz:
Direct Product Testing With Nearly Identical Sets. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j7]Subhash Khot, Dana Moshkovitz:
NP-Hardness of Approximately Solving Linear Equations over Reals. SIAM J. Comput. 42(3): 752-791 (2013) - [c8]Pasin Manurangsi, Dana Moshkovitz:
Improved Approximation Algorithms for Projection Games - (Extended Abstract). ESA 2013: 683-694 - [c7]Vitaly Abdrashitov, Muriel Médard, Dana Moshkovitz:
Matched filter decoding of random binary and Gaussian codes in broadband Gaussian channel. ISIT 2013: 2528-2523 - 2012
- [j6]Dana Moshkovitz:
The tale of the PCP theorem. XRDS 18(3): 23-26 (2012) - [j5]Dana Moshkovitz:
Guest column: algebraic construction of projection PCPs. SIGACT News 43(1): 62-81 (2012) - [c6]Dana Moshkovitz:
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. APPROX-RANDOM 2012: 276-287 - 2011
- [c5]Subhash Khot, Dana Moshkovitz:
NP-hardness of approximately solving linear equations over reals. STOC 2011: 413-420 - [i8]Dana Moshkovitz:
The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j4]Dana Moshkovitz, Ran Raz
:
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size. Comput. Complex. 19(3): 367-422 (2010) - [j3]Dana Moshkovitz, Ran Raz
:
Two-query PCP with subconstant error. J. ACM 57(5): 29:1-29:29 (2010) - [c4]Adi Akavia, Oded Goldreich
, Shafi Goldwasser, Dana Moshkovitz:
Erratum for: on basing one-way functions on NP-hardness. STOC 2010: 795-796 - [i7]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 abs/1002.3864 (2010) - [i6]Subhash Khot, Dana Moshkovitz:
NP-Hardness of Approximately Solving Linear Equations Over Reals. Electron. Colloquium Comput. Complex. TR10 (2010) - [i5]Dana Moshkovitz:
An Alternative Proof of The Schwartz-Zippel Lemma. Electron. Colloquium Comput. Complex. TR10 (2010) - [i4]Dana Moshkovitz, Subhash Khot:
Hardness of Approximately Solving Linear Equations Over Reals. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2008
- [j2]Dana Moshkovitz, Ran Raz
:
Sub-Constant Error Low Degree Test of Almost-Linear Size. SIAM J. Comput. 38(1): 140-180 (2008) - [c3]Dana Moshkovitz, Ran Raz
:
Two Query PCP with Sub-Constant Error. FOCS 2008: 314-323 - [i3]Dana Moshkovitz, Ran Raz:
Two Query PCP with Sub-Constant Error. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [i2]Dana Moshkovitz, Ran Raz:
Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j1]Noga Alon, Dana Moshkovitz, Shmuel Safra
:
Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2): 153-177 (2006) - [c2]Dana Moshkovitz, Ran Raz
:
Sub-constant error low degree test of almost-linear size. STOC 2006: 21-30 - [c1]Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz:
On basing one-way functions on NP-hardness. STOC 2006: 701-710 - 2005
- [i1]Dana Moshkovitz, Ran Raz:
Sub-Constant Error Low Degree Test of Almost Linear Size. Electron. Colloquium Comput. Complex. TR05 (2005)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-10 01:26 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint