| 2026 | SODA | On the Usefulness of Promises. | Per Austrin, Johan Hstad, Bjrn Martinsson |
| 2023 | FOCS | On small-depth Frege proofs for PHP. | Johan Hstad |
| 2022 | FOCS | On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. | Johan Hstad, Kilian Risse |
| 2021 | SODA | Optimal Inapproximability with Universal Factor Graphs. | Per Austrin, Jonah Brown-Cohen, Johan Hstad |
| 2021 | SODA | Explicit two-deletion codes with redundancy matching the existential bound. | Venkatesan Guruswami, Johan Hstad |
| 2018 | FOCS | Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs. | Johan Hstad |
| 2017 | FOCS | On Small-Depth Frege Proofs for Tseitin for Grids. | Johan Hstad |
| 2017 | PQCrypto | Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. | Martin Eker, Johan Hstad |
| 2016 | FOCS | An Average-Case Depth Hierarchy Theorem for Higher Depth. | Johan Hstad |
| 2014 | FOCS | (2 + epsilon)-Sat Is NP-Hard. | Per Austrin, Johan Hstad, Venkatesan Guruswami |
| 2014 | ICALP | On DNF Approximators for Monotone Boolean Functions. | Eric Blais, Johan Hstad, Rocco A. Servedio, Li-Yang Tan |
| 2014 | STOC | Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. | Venkatesan Guruswami, Prahladh Harsha, Johan Hstad, Srikanth Srinivasan, Girish Varma |
| 2012 | FOCS | Making the Long Code Shorter. | Boaz Barak, Parikshit Gopalan, Johan Hstad, Raghu Meka, Prasad Raghavendra, David Steurer |
| 2010 | STOC | On the list-decodability of random linear codes. | Venkatesan Guruswami, Johan Hstad, Swastik Kopparty |
| 2010 | TCC | An Efficient Parallel Repetition Theorem. | Johan Hstad, Rafael Pass, Douglas Wikstrm, Krzysztof Pietrzak |
| 2009 | STOC | Randomly supported independence and resistance. | Per Austrin, Johan Hstad |
| 2008 | STOC | Towards an optimal separation of space and length in resolution. | Jakob Nordstrm, Johan Hstad |
| 2005 | STOC | Every 2-CSP allows nontrivial approximation. | Johan Hstad |
| 2004 | CRYPTO | Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. | Yevgeniy Dodis, Rosario Gennaro, Johan Hstad, Hugo Krawczyk, Tal Rabin |
| 2002 | STOC | On the advantage over a random assignment. | Johan Hstad, Srinivasan Venkatesh |
| 2001 | ASIACRYPT | Practical Construction and Analysis of Pseudo-Randomness Primitives. | Johan Hstad, Mats Nslund |
| 2001 | FOCS | Query Efficient PCPs with Perfect Completeness. | Johan Hstad, Subhash Khot |
| 2000 | CCS | Funkspiel schemes: an alternative to conventional tamper resistance. | Johan Hstad, Jakob Jonsson, Ari Juels, Moti Yung |
| 2000 | FOCS | Hardness of Approximate Hypergraph Coloring. | Venkatesan Guruswami, Johan Hstad, Madhu Sudan |
| 2000 | ICALP | Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? | Johan Hstad |
| 1999 | SODA | A New Way to Use Semidefinite Programming with Applications to Linear Equations mod | Gunnar Andersson, Lars Engebretsen, Johan Hstad |
| 1998 | ESA | Fitting Points on the Real Line and Its Application to RH Mapping. | Johan Hstad, Lars Ivansson, Jens Lagergren |
| 1998 | FOCS | The Security of Individual RSA Bits. | Johan Hstad, Mats Nslund |
| 1997 | STOC | Some Optimal Inapproximability Results. | Johan Hstad |
| 1996 | FOCS | Clique is Hard to Approximate Within n | Johan Hstad |
| 1996 | STOC | Testing of the Long Code and Hardness for Clique. | Johan Hstad |
| 1995 | FOCS | Linearity Testing in Characteristic Two. | Mihir Bellare, Don Coppersmith, Johan Hstad, Marcos A. Kiwi, Madhu Sudan |
| 1995 | STOC | A tight lower bound for searching a sorted array. | Arne Andersson, Johan Hstad, Ola Petersson |
| 1995 | STOC | Monotone circuits for connectivity have depth (log n) | Mikael Goldmann, Johan Hstad |
| 1994 | STOC | The complexity of searching a sorted array of strings. | Arne Andersson, Torben Hagerup, Johan Hstad, Ola Petersson |
| 1993 | FOCS | The shrinkage exponent is 2 | Johan Hstad |
| 1993 | FOCS | Top-Down Lower Bounds for Depth 3 Circuits | Johan Hstad, Stasys Jukna, Pavel Pudlk |
| 1990 | FOCS | Simple Constructions of Almost k-Wise Independent Random Variables | Noga Alon, Oded Goldreich, Johan Hstad, Ren Peralta |
| 1990 | FOCS | On the Power of Small-Depth Threshold Circuits | Johan Hstad, Mikael Goldmann |
| 1990 | STOC | Pseudo-Random Generators under Uniform Assumptions | Johan Hstad |
| 1989 | ICALP | Tensor Rank is NP-Complete. | Johan Hstad |
| 1989 | STOC | Fast Computation Using Faulty Hypercubes (Extended Abstract) | Johan Hstad, Frank Thomson Leighton, Mark Newman |
| 1988 | CRYPTO | Everything Provable is Provable in Zero-Knowledge. | Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Hstad, Joe Kilian, Silvio Micali, Phillip Rogaway |
| 1987 | FOCS | Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds | William Aiello, Johan Hstad |
| 1987 | STOC | Optimal Bounds for Decision Problems on the CRCW PRAM | Paul Beame, Johan Hstad |
| 1987 | STOC | Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract) | Johan Hstad, Frank Thomson Leighton, Mark Newman |
| 1987 | STOC | Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract) | Johan Hstad, Frank Thomson Leighton, Brian Rogoff |
| 1986 | FOCS | On the Power of Interaction | William Aiello, Shafi Goldwasser, Johan Hstad |
| 1986 | STOC | Almost Optimal Lower Bounds for Small Depth Circuits | Johan Hstad |
| 1986 | STACS | Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers. | Johan Hstad, Bettina Helfrich, J. C. Lagarias, Claus-Peter Schnorr |
| 1985 | CRYPTO | On Using RSA with Low Exponent in a Public Key Network. | Johan Hstad |
| 1985 | FOCS | The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) | Benny Chor, Oded Goldreich, Johan Hstad, Joel Friedman, Steven Rudich, Roman Smolensky |
| 1985 | STOC | The Cryptographic Security of Truncated Linearly Related Variables | Johan Hstad, Adi Shamir |