Amplification and Derandomization without Slowdown. | 0 | 0.34 | 2020 |
Small Set Expansion in The Johnson Graph. | 0 | 0.34 | 2018 |
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. | 2 | 0.39 | 2018 |
Mixing Implies Lower Bounds for Space Bounded Learning. | 4 | 0.45 | 2017 |
Approximation Algorithms for Label Cover and The Log-Density Threshold. | 3 | 0.41 | 2017 |
Low-degree test with polynomially small error. | 1 | 0.35 | 2017 |
Mixing Implies Strong Lower Bounds for Space Bounded Learning. | 1 | 0.38 | 2017 |
Candidate hard unique game. | 6 | 0.53 | 2016 |
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. | 1 | 0.35 | 2016 |
Amplification and Derandomization without Slowdown | 0 | 0.34 | 2015 |
Approximating Dense Max 2-CSPs | 1 | 0.35 | 2015 |
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. | 40 | 1.38 | 2015 |
AM with Multiple Merlins | 21 | 0.74 | 2014 |
Parallel Repetition of Fortified Games. | 1 | 0.36 | 2014 |
An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing. | 4 | 0.42 | 2014 |
NP-Hardness of Approximately Solving Linear Equations Over Reals | 6 | 0.48 | 2013 |
Improved Approximation Algorithms for Projection Games - (Extended Abstract). | 0 | 0.34 | 2013 |
The tale of the PCP theorem | 0 | 0.34 | 2012 |
Guest column: algebraic construction of projection PCPs | 0 | 0.34 | 2012 |
An Alternative Proof of The Schwartz-Zippel Lemma | 3 | 0.43 | 2010 |
Two-query PCP with subconstant error | 65 | 1.73 | 2010 |
Erratum for: on basing one-way functions on NP-hardness | 1 | 0.42 | 2010 |
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) | 0 | 0.34 | 2010 |
Sub-Constant Error Low Degree Test of Almost Linear Size | 17 | 0.77 | 2008 |
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size | 8 | 0.51 | 2007 |
Algorithmic construction of sets for k-restrictions | 150 | 5.13 | 2006 |
On basing one-way functions on NP-hardness | 33 | 1.18 | 2006 |