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
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
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
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
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
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
Query Efficient PCPs with Perfect Completeness
by Johan Håstad and Subhash Khot