Articles by Johan Håstad
Vol 13, Article 19 (pp 1-51)
[APRX-RND15 Spec Issue]
Improved NP-Inapproximability for $2$-Variable Linear Equations by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright |
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin by Johan Håstad and Rajsekar Manokaran |
Vol 9, Article 27 (pp 845-862)
[Boolean Spec Issue]
Satisfying Degree-$d$ Equations over $GF[2]^n$ by Johan Håstad |
Vol 9, Article 14 (pp 471-557)
Towards an Optimal Separation of Space and Length in Resolution by Jakob Nordström and Johan Håstad |
Vol 3, Article 11 (pp 211-219)
The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson |
Vol 1, Article 7 (pp 119-148)
Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot |