Johan Håstad

ORCID

Publication Activity (10 Years)

Years Active: 1985-2024
Publications (10 Years): 36

Top Venues

FOCS

SIAM J. Comput.

CoRR

Electron. Colloquium Comput. Complex.

Publications

Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima, Stanislav Zivný
A logarithmic approximation of linearly-ordered colourings. CoRR (2024)
Johan Håstad
On Small-depth Frege Proofs for PHP. CoRR (2024)
Johan Håstad
On small-depth Frege proofs for PHP. Electron. Colloquium Comput. Complex. (2023)
Johan Håstad
On small-depth Frege proofs for PHP. FOCS (2023)
Johan Håstad
The EATCS Award 2023 - Laudatio for Amos Fiat. Bull. EATCS 140 (2023)
Johan Håstad, Kilian Risse
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. FOCS (2022)
Johan Håstad, Kilian Risse
On bounded depth proofs for Tseitin formulas on the grid; revisited. CoRR (2022)
Johan Håstad
The EATCS Award 2023 - Call for Nominations. Bull. EATCS 138 (2022)
Venkatesan Guruswami, Johan Håstad
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound. IEEE Trans. Inf. Theory 67 (10) (2021)
Johan Håstad
On Small-depth Frege Proofs for Tseitin for Grids. J. ACM 68 (1) (2021)
Venkatesan Guruswami, Johan Håstad
Explicit two-deletion codes with redundancy matching the existential bound. SODA (2021)
Per Austrin, Jonah Brown-Cohen, Johan Håstad
Optimal Inapproximability with Universal Factor Graphs. SODA (2021)
Johan Håstad, Guillaume Lagarde, Joseph Swernofsky
d-Galvin Families. Electron. J. Comb. 27 (1) (2020)
Venkatesan Guruswami, Johan Håstad
Explicit two-deletion codes with redundancy matching the existential bound. CoRR (2020)
Marta Kwiatkowska, Éva Tardos, Johan Håstad
The EATCS Award 2021 - Call for Nominations. Bull. EATCS 132 (2020)
Per Austrin, Jonah Brown-Cohen, Johan Håstad
Optimal Inapproximability with Universal Factor Graphs. Electron. Colloquium Comput. Complex. 26 (2019)
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
Bounded Independence versus Symmetric Tests. ACM Trans. Comput. Theory 11 (4) (2019)
Johan Håstad
Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs. FOCS (2018)
Martin Ekerå, Johan Håstad
Quantum algorithms for computing short discrete logarithms and factoring RSA integers. CoRR (2017)
Johan Håstad
On small-depth Frege proofs for Tseitin for grids. Electron. Colloquium Comput. Complex. 24 (2017)
Boris Bukh, Venkatesan Guruswami, Johan Håstad
An Improved Bound on the Fraction of Correctable Deletions. IEEE Trans. Inf. Theory 63 (1) (2017)
Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes. SIAM J. Comput. 46 (1) (2017)
Johan Håstad, Rajsekar Manokaran
On the Hardness of Approximating Balanced Homogenous 3-Lin. Theory Comput. 13 (1) (2017)
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
Improved NP-Inapproximability for 2-Variable Linear Equations. Theory Comput. 13 (1) (2017)
Per Austrin, Venkatesan Guruswami, Johan Håstad
(2+ε)-Sat Is NP-hard. SIAM J. Comput. 46 (5) (2017)
Johan Håstad
On Small-Depth Frege Proofs for Tseitin for Grids. FOCS (2017)
Martin Ekerå, Johan Håstad
Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. PQCrypto (2017)
Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. J. ACM 64 (5) (2017)
Martin Ekerå, Johan Håstad
Quantum algorithms for computing short discrete logarithms and factoring RSA integers. IACR Cryptol. ePrint Arch. 2017 (2017)
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
Bounded independence vs. moduli. Electron. Colloquium Comput. Complex. 23 (2016)
Johan Håstad
An Average-Case Depth Hierarchy Theorem for Higher Depth. FOCS (2016)
Johan Håstad
The square lattice shuffle, correction. Random Struct. Algorithms 48 (1) (2016)
Johan Håstad
An average-case depth hierarchy theorem for higher depth. Electron. Colloquium Comput. Complex. 23 (2016)
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
Bounded Independence vs. Moduli. APPROX-RANDOM (2016)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. SIAM J. Comput. 44 (5) (2015)
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
Improved NP-Inapproximability for 2-Variable Linear Equations. APPROX-RANDOM (2015)
Per Austrin, Johan Håstad, Venkatesan Guruswami
(2 + epsilon)-Sat Is NP-Hard. FOCS (2014)
Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan
On DNF Approximators for Monotone Boolean Functions. ICALP (1) (2014)
Johan Håstad
On the NP-Hardness of Max-Not-2. SIAM J. Comput. 43 (1) (2014)
Johan Håstad
On the Correlation of Parity and Small-Depth Circuits. SIAM J. Comput. 43 (5) (2014)
Johan Håstad, Bettina Just, J. C. Lagarias, Claus-Peter Schnorr
Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers. SIAM J. Comput. 43 (1) (2014)
Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. STOC (2014)
Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Electron. Colloquium Comput. Complex. 20 (2013)
Per Austrin, Venkatesan Guruswami, Johan Håstad
(2+ε)-SAT is NP-hard. Electron. Colloquium Comput. Complex. 20 (2013)
Jakob Nordström, Johan Håstad
Towards an Optimal Separation of Space and Length in Resolution. Theory Comput. 9 (2013)
Per Austrin, Johan Håstad, Rafael Pass
On the power of many one-bit provers. ITCS (2013)
Johan Håstad
. Theory Comput. 9 (2013)
Venkatesan Guruswami, Johan Håstad, Prahladh Harsha, Srikanth Srinivasan, Girish Varma
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. CoRR (2013)
Per Austrin, Johan Håstad, Rafael Pass
On the Power of Many One-Bit Provers CoRR (2013)
Per Austrin, Johan Håstad
On the usefulness of predicates. ACM Trans. Comput. Theory 5 (1) (2013)
Per Austrin, Johan Håstad
On the Usefulness of Predicates. Computational Complexity Conference (2012)
Johan Håstad
On the correlation of parity and small-depth circuits. Electron. Colloquium Comput. Complex. 19 (2012)
Johan Håstad, Andrei A. Krokhin, Dániel Marx
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). Dagstuhl Reports 2 (11) (2012)
Johan Håstad
On the NP-Hardness of Max-Not-2. APPROX-RANDOM (2012)
Per Austrin, Johan Håstad
On the Usefulness of Predicates CoRR (2012)
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
Approximating Linear Threshold Predicates. ACM Trans. Comput. Theory 4 (1) (2012)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. FOCS (2012)
Johan Håstad
Satisfying Degree-d Equations over GF[2] n. APPROX-RANDOM (2011)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the long code shorter, with applications to the Unique Games Conjecture CoRR (2011)
Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. 40 (3) (2011)
Per Austrin, Johan Håstad
Randomly Supported Independence and Resistance. SIAM J. Comput. 40 (1) (2011)
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
On the List-Decodability of Random Linear Codes. IEEE Trans. Inf. Theory 57 (2) (2011)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the long code shorter, with applications to the Unique Games Conjecture. Electron. Colloquium Comput. Complex. 18 (2011)
Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electron. Colloquium Comput. Complex. 18 (2011)
Johan Håstad, Rafael Pass, Douglas Wikström, Krzysztof Pietrzak
An Efficient Parallel Repetition Theorem. TCC (2010)
Johan Håstad
Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword. Comput. Complex. 19 (2) (2010)
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
On the List-Decodability of Random Linear Codes CoRR (2010)
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
Approximating Linear Threshold Predicates. Electron. Colloquium Comput. Complex. 17 (2010)
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
On the list-decodability of random linear codes. STOC (2010)
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
On the List-Decodability of Random Linear Codes. Electron. Colloquium Comput. Complex. 17 (2010)
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
Approximating Linear Threshold Predicates. APPROX-RANDOM (2010)
Per Austrin, Johan Håstad
Randomly supported independence and resistance. STOC (2009)
Johan Håstad
On the Approximation Resistance of a Random Predicate. Comput. Complex. 18 (3) (2009)
Johan Håstad
Every 2-csp Allows Nontrivial Approximation. Comput. Complex. 17 (4) (2008)
Jakob Nordström, Johan Håstad
Towards an optimal separation of space and length in resolution. STOC (2008)
Jakob Nordström, Johan Håstad
Towards an Optimal Separation of Space and Length in Resolution CoRR (2008)
Johan Håstad, Mats Näslund
Practical Construction and Analysis of Pseudo-Randomness Primitives. J. Cryptol. 21 (1) (2008)
Jakob Nordström, Johan Håstad
Towards an Optimal Separation of Space and Length in Resolution. Electron. Colloquium Comput. Complex. 15 (026) (2008)
Johan Håstad, Avi Wigderson
The Randomized Communication Complexity of Set Disjointness. Theory Comput. 3 (1) (2007)
Johan Håstad
On the Approximation Resistance of a Random Predicate. APPROX-RANDOM (2007)
Johan Håstad, Svante Linusson, Johan Wästlund
A Smaller Sleeping Bag for a Baby Snake. Discret. Comput. Geom. 38 (1) (2007)
Johan Håstad
The Security of the IAPM and IACBC Modes. J. Cryptol. 20 (2) (2007)
Johan Håstad
On Nontrivial Approximation of CSPs. APPROX-RANDOM (2006)
Johan Håstad
The square lattice shuffle. Random Struct. Algorithms 29 (4) (2006)
Johan Håstad, Subhash Khot
Query Efficient PCPs with Perfect Completeness. Theory Comput. 1 (1) (2005)
Johan Håstad
Every 2-CSP allows nontrivial approximation. STOC (2005)
Johan Håstad, Srinivasan Venkatesh
On the advantage over a random assignment. Random Struct. Algorithms 25 (2) (2004)
Yevgeniy Dodis, Rosario Gennaro, Johan Håstad, Hugo Krawczyk, Tal Rabin
Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. CRYPTO (2004)
Johan Håstad, Mats Näslund
The security of all RSA and discrete log bits. J. ACM 51 (2) (2004)
Johan Håstad
Inapproximability Some history and some open problems. Computational Complexity Conference (2003)
Johan Håstad, Lars Ivansson, Jens Lagergren
Fitting points on the real line and its application to RH mapping. J. Algorithms 49 (1) (2003)
Johan Håstad, Avi Wigderson
Simple analysis of graph tests for linearity and PCP. Random Struct. Algorithms 22 (2) (2003)
Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman
Combinatorial bounds for list decoding. IEEE Trans. Inf. Theory 48 (5) (2002)
Johan Håstad, Srinivasan Venkatesh
On the advantage over a random assignment. STOC (2002)
Venkatesan Guruswami, Johan Håstad, Madhu Sudan
Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31 (6) (2002)
Gunnar Andersson, Lars Engebretsen, Johan Håstad
A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p. J. Algorithms 39 (2) (2001)
Dorit Dor, Johan Håstad, Staffan Ulfberg, Uri Zwick
On Lower Bounds for Selecting the Median. SIAM J. Discret. Math. 14 (3) (2001)
Johan Håstad, Avi Wigderson
Simple Analysis of Graph Tests for Linearity and PCP. Computational Complexity Conference (2001)
Johan Håstad, Mats Näslund
Practical Construction and Analysis of Pseudo-Randomness Primitives. ASIACRYPT (2001)
Johan Håstad, Svante Linusson, Johan Wästlund
A Smaller Sleeping Bag for a Baby Snake. Discret. Comput. Geom. 26 (1) (2001)

Johan Håstad.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Johan Håstad