On Using RSA with Low Exponent in a Public Key Network. - Johan Håstad (CRYPTO, 1985)

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) - Benny Chor; Oded Goldreich 001; Johan Håstad; Joel Friedman; Steven Rudich; Roman Smolensky (FOCS, 1985)

The Cryptographic Security of Truncated Linearly Related Variables - Johan Håstad; Adi Shamir (STOC, 1985)

Almost Optimal Lower Bounds for Small Depth Circuits - Johan Håstad (STOC, 1986)

Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds - William Aiello; Johan Håstad (FOCS, 1987)

Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract) - Johan Håstad; Frank Thomson Leighton; Mark Newman (STOC, 1987)

Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract) - Johan Håstad; Frank Thomson Leighton; Brian Rogoff (STOC, 1987)

Does co-NP Have Short Interactive Proofs? - Ravi B. Boppana; Johan Håstad; Stathis Zachos (Inf. Process. Lett., 1987)

One-Way Permutations in NC0. - Johan Håstad (Inf. Process. Lett., 1987)

Everything Provable is Provable in Zero-Knowledge. - Michael Ben-Or; Oded Goldreich 001; Shafi Goldwasser; Johan Håstad; Joe Kilian; Silvio Micali; Phillip Rogaway (CRYPTO, 1988)

Dual vectors and lower bounds for the nearest lattice point problem. - Johan Håstad (Comb., 1988)

Reconstructing Truncated Integer Variables Satisfying Linear Congruences. - Alan M. Frieze; Johan Håstad; Ravi Kannan; J. C. Lagarias 001; Adi Shamir (SIAM J. Comput., 1988)

Solving Simultaneous Modular Equations of Low Degree. - Johan Håstad (SIAM J. Comput., 1988)

Fast Computation Using Faulty Hypercubes (Extended Abstract) - Johan Håstad; Frank Thomson Leighton; Mark Newman (STOC, 1989)

Optimal bounds for decision problems on the CRCW PRAM. - Paul Beame; Johan Håstad (J. ACM, 1989)

Polynomial Time Algorithms for Finding Integer Relations among Real Numbers. - Johan Håstad; Bettina Just; J. C. Lagarias 001; Claus-Peter Schnorr (SIAM J. Comput., 1989)

Composition of the Universal Relation. - Johan Håstad; Avi Wigderson (Advances In Computational Complexity Theory, 1990)

Simple Constructions of Almost k-Wise Independent Random Variables - Noga Alon; Oded Goldreich 001; Johan Håstad; René Peralta 001 (FOCS, 1990)

Pseudo-Random Generators under Uniform Assumptions - Johan Håstad (STOC, 1990)

On the power of interaction. - William Aiello; Shafi Goldwasser; Johan Håstad (Comb., 1990)

Tensor Rank is NP-Complete. - Johan Håstad (J. Algorithms, 1990)

On the Power of Small-Depth Threshold Circuits. - Johan Håstad; Mikael Goldmann (Comput. Complex., 1991)

Statistical Zero-Knowledge Languages can be Recognized in Two Rounds. - William Aiello; Johan Håstad (J. Comput. Syst. Sci., 1991)

Relativized Perfect Zero Knowledge Is Not BPP - William Aiello; Johan Håstad (Inf. Comput., 1991)

Majority Gates VS. General Weighted Threshold Gates. - Mikael Goldmann; Johan Håstad; Alexander A. Razborov (Comput. Complex., 1992)

A Simple Lower Bound for Monotone Clique Using a Communication Game. - Mikael Goldmann; Johan Håstad (Inf. Process. Lett., 1992)

Simple Construction of Almost k-wise Independent Random Variables. - Noga Alon; Oded Goldreich 001; Johan Håstad; René Peralta 001 (Random Struct. Algorithms, 1992)

The shrinkage exponent is 2 - Johan Håstad (FOCS, 1993)

Top-Down Lower Bounds for Depth 3 Circuits - Johan Håstad; Stasys Jukna; Pavel Pudlák (FOCS, 1993)

A Well-Characterized Approximation Problem. - Johan Håstad; Steven J. Phillips; Shmuel Safra (Inf. Process. Lett., 1993)

The Discrete Logarithm Modulo a Composite Hides O(n) Bits. - Johan Håstad; A. W. Schrift; Adi Shamir (J. Comput. Syst. Sci., 1993)

Addendum to "Simple Construction of Almost k-wise Independent Random Variables". - Noga Alon; Oded Goldreich 001; Johan Håstad; René Peralta 001 (Random Struct. Algorithms, 1993)

The complexity of searching a sorted array of strings. - Arne Andersson; Torben Hagerup; Johan Håstad; Ola Petersson (STOC, 1994)

Recent Results in Hardness of Approximation. - Johan Håstad (SWAT, 1994)

On Average Time Hierarchies. - Mikael Goldmann; Per Grape; Johan Håstad (Inf. Process. Lett., 1994)

The Random Oracle Hypothesis Is False. - Richard Chang 001; Benny Chor; Oded Goldreich 001; Juris Hartmanis; Johan Håstad; Desh Ranjan; Pankaj Rohatgi (J. Comput. Syst. Sci., 1994)

On the Size of Weights for Threshold Gates. - Johan Håstad (SIAM J. Discret. Math., 1994)

Optimal Depth, Very Small Size Circuits for Symmetric Functions in AC0. - Johan Håstad; Ingo Wegener; Norbert Wurm; Sang-Zin Yi (Inf. Comput., 1994)

A tight lower bound for searching a sorted array. - Arne Andersson; Johan Håstad; Ola Petersson (STOC, 1995)

Monotone circuits for connectivity have depth (log n)2-o(1) (Extended Abstract). - Mikael Goldmann; Johan Håstad (STOC, 1995)

Top-Down Lower Bounds for Depth-Three Circuits. - Johan Håstad; Stasys Jukna; Pavel Pudlák (Comput. Complex., 1995)

On the Shrinkage Exponent for Read-Once Formulae. - Johan Håstad; Alexander A. Razborov; Andrew Chi-Chih Yao (Theor. Comput. Sci., 1995)

Testing of the Long Code and Hardness for Clique. - Johan Håstad (STOC, 1996)

On the Message Complexity of Interactive Proof Systems - Oded Goldreich 001; Johan Håstad (Electron. Colloquium Comput. Complex., 1996)

Analysis of Backoff Protocols for Multiple Access Channels. - Johan Håstad; Frank Thomson Leighton; Brian Rogoff (SIAM J. Comput., 1996)

Linearity testing in characteristic two. - Mihir Bellare; Don Coppersmith; Johan Håstad; Marcos A. Kiwi; Madhu Sudan 001 (IEEE Trans. Inf. Theory, 1996)

Some optimal inapproximability results - Johan Håstad (Electron. Colloquium Comput. Complex., 1997)

Clique is hard to approximate within n1-epsilon - Johan Håstad (Electron. Colloquium Comput. Complex., 1997)

The Security of Individual RSA Bits. - Johan Håstad; Mats Näslund (FOCS, 1998)

Some Recent Strong Inapproximability Results. - Johan Håstad (SWAT, 1998)

On the Complexity of Interactive Proofs with Bounded Communication. - Oded Goldreich 001; Johan Håstad (Inf. Process. Lett., 1998)

Circuit Bottom Fan-In and Computational Power. - Liming Cai; Jianer Chen; Johan Håstad (SIAM J. Comput., 1998)

Monotone Circuits for Connectivity Have Depth (log n)2-o(1). - Mikael Goldmann; Johan Håstad (SIAM J. Comput., 1998)

The Shrinkage Exponent of de Morgan Formulas is 2. - Johan Håstad (SIAM J. Comput., 1998)

A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p. - Gunnar Andersson; Lars Engebretsen; Johan Håstad (SODA, 1999)

The Security of all RSA and Discrete Log Bits - Johan Håstad; Mats Näslund (Electron. Colloquium Comput. Complex., 1999)

On approximating CSP-B - Johan Håstad (Electron. Colloquium Comput. Complex., 1999)

A Pseudorandom Generator from any One-way Function. - Johan Håstad; Russell Impagliazzo; Leonid A. Levin; Michael Luby (SIAM J. Comput., 1999)

Funkspiel schemes: an alternative to conventional tamper resistance. - Johan Håstad; Jakob Jonsson; Ari Juels; Moti Yung (CCS, 2000)

Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? - Johan Håstad (ICALP, 2000)

On bounded occurrence constraint satisfaction. - Johan Håstad (Inf. Process. Lett., 2000)

Tight Bounds for Searching a Sorted Array of Strings. - Arne Andersson; Torben Hagerup; Johan Håstad; Ola Petersson (SIAM J. Comput., 2000)

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p. - Gunnar Andersson; Lars Engebretsen; Johan Håstad (J. Algorithms, 2001)

Linear-Consistency Testing. - Yonatan Aumann; Johan Håstad; Michael O. Rabin; Madhu Sudan 001 (J. Comput. Syst. Sci., 2001)

A Slight Sharpening of LMN. - Johan Håstad (J. Comput. Syst. Sci., 2001)

On Lower Bounds for Selecting the Median. - Dorit Dor; Johan Håstad; Staffan Ulfberg; Uri Zwick (SIAM J. Discret. Math., 2001)

Hardness of Approximate Hypergraph Coloring. - Venkatesan Guruswami; Johan Håstad; Madhu Sudan 001 (SIAM J. Comput., 2002)

Combinatorial bounds for list decoding. - Venkatesan Guruswami; Johan Håstad; Madhu Sudan 001; David Zuckerman (IEEE Trans. Inf. Theory, 2002)

Inapproximability Some history and some open problems. - Johan Håstad (CCC, 2003)

Fitting points on the real line and its application to RH mapping. - Johan Håstad; Lars Ivansson; Jens Lagergren (J. Algorithms, 2003)

Simple analysis of graph tests for linearity and PCP. - Johan Håstad; Avi Wigderson (Random Struct. Algorithms, 2003)

Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. - Yevgeniy Dodis; Rosario Gennaro; Johan Håstad; Hugo Krawczyk; Tal Rabin (CRYPTO, 2004)

On the advantage over a random assignment. - Johan Håstad; Srinivasan Venkatesh 001 (Random Struct. Algorithms, 2004)

Query Efficient PCPs with Perfect Completeness. - Johan Håstad; Subhash Khot (Theory Comput., 2005)

On Nontrivial Approximation of CSPs. - Johan Håstad (APPROX-RANDOM, 2006)

The square lattice shuffle. - Johan Håstad (Random Struct. Algorithms, 2006)

A Smaller Sleeping Bag for a Baby Snake. - Johan Håstad; Svante Linusson; Johan Wästlund (Discret. Comput. Geom., 2007)

The Security of the IAPM and IACBC Modes. - Johan Håstad (J. Cryptol., 2007)

The Randomized Communication Complexity of Set Disjointness. - Johan Håstad; Avi Wigderson (Theory Comput., 2007)

Every 2-csp Allows Nontrivial Approximation. - Johan Håstad (Comput. Complex., 2008)

Towards an Optimal Separation of Space and Length in Resolution. - Jakob Nordström; Johan Håstad (Electron. Colloquium Comput. Complex., 2008)

Practical Construction and Analysis of Pseudo-Randomness Primitives. - Johan Håstad; Mats Näslund (J. Cryptol., 2008)

On the Approximation Resistance of a Random Predicate. - Johan Håstad (Comput. Complex., 2009)

An Efficient Parallel Repetition Theorem. - Johan Håstad; Rafael Pass; Douglas Wikström; Krzysztof Pietrzak (TCC, 2010)

Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword. - Johan Håstad (Comput. Complex., 2010)

Approximating Linear Threshold Predicates. - Mahdi Cheraghchi; Johan Håstad; Marcus Isaksson; Ola Svensson (Electron. Colloquium Comput. Complex., 2010)

On the List-Decodability of Random Linear Codes. - Venkatesan Guruswami; Johan Håstad; Swastik Kopparty (Electron. Colloquium Comput. Complex., 2010)

Satisfying Degree-d Equations over GF[2] n. - Johan Håstad (APPROX-RANDOM, 2011)

Making the long code shorter, with applications to the Unique Games Conjecture. - Boaz Barak; Parikshit Gopalan; Johan Håstad; Raghu Meka; Prasad Raghavendra; David Steurer (Electron. Colloquium Comput. Complex., 2011)

Randomly Supported Independence and Resistance. - Per Austrin; Johan Håstad (SIAM J. Comput., 2011)

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. - Venkatesan Guruswami; Johan Håstad; Rajsekar Manokaran; Prasad Raghavendra; Moses Charikar (SIAM J. Comput., 2011)

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). - Johan Håstad; Andrei A. Krokhin; Dániel Marx (Dagstuhl Reports, 2012)

On the power of many one-bit provers. - Per Austrin; Johan Håstad; Rafael Pass (ITCS, 2013)

Satisfying Degree-d Equations over GF[2]n. - Johan Håstad (Theory Comput., 2013)

On the usefulness of predicates. - Per Austrin; Johan Håstad (ACM Trans. Comput. Theory, 2013)

(2 + epsilon)-Sat Is NP-Hard. - Per Austrin; Johan Håstad; Venkatesan Guruswami (FOCS, 2014)

On DNF Approximators for Monotone Boolean Functions. - Eric Blais; Johan Håstad; Rocco A. Servedio; Li-Yang Tan (ICALP (1), 2014)

On the NP-Hardness of Max-Not-2. - Johan Håstad (SIAM J. Comput., 2014)

On the Correlation of Parity and Small-Depth Circuits. - Johan Håstad (SIAM J. Comput., 2014)

Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers. - Johan Håstad; Bettina Just; J. C. Lagarias 001; Claus-Peter Schnorr (SIAM J. Comput., 2014)

Making the Long Code Shorter. - Boaz Barak; Parikshit Gopalan; Johan Håstad; Raghu Meka; Prasad Raghavendra; David Steurer (SIAM J. Comput., 2015)

Bounded independence vs. moduli. - Ravi B. Boppana; Johan Håstad; Chin Ho Lee; Emanuele Viola (Electron. Colloquium Comput. Complex., 2016)

An average-case depth hierarchy theorem for higher depth. - Johan Håstad (Electron. Colloquium Comput. Complex., 2016)

The square lattice shuffle, correction. - Johan Håstad (Random Struct. Algorithms, 2016)

On small-depth Frege proofs for Tseitin for grids. - Johan Håstad (Electron. Colloquium Comput. Complex., 2017)

Quantum algorithms for computing short discrete logarithms and factoring RSA integers. - Martin Ekerå; Johan Håstad (IACR Cryptol. ePrint Arch., 2017)

An Average-Case Depth Hierarchy Theorem for Boolean Circuits. - Johan Håstad; Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (J. ACM, 2017)

(2+ε)-Sat Is NP-hard. - Per Austrin; Venkatesan Guruswami; Johan Håstad (SIAM J. Comput., 2017)

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes. - Venkatesan Guruswami; Prahladh Harsha; Johan Håstad; Srikanth Srinivasan 001; Girish Varma (SIAM J. Comput., 2017)

An Improved Bound on the Fraction of Correctable Deletions. - Boris Bukh; Venkatesan Guruswami; Johan Håstad (IEEE Trans. Inf. Theory, 2017)

Improved NP-Inapproximability for 2-Variable Linear Equations. - Johan Håstad; Sangxia Huang; Rajsekar Manokaran; Ryan O'Donnell; John Wright 004 (Theory Comput., 2017)

On the Hardness of Approximating Balanced Homogenous 3-Lin. - Johan Håstad; Rajsekar Manokaran (Theory Comput., 2017)

Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs. - Johan Håstad (FOCS, 2018)

Following a tangent of proofs. - Johan Håstad (Providing Sound Foundations for Cryptography, 2019)

Optimal Inapproximability with Universal Factor Graphs. - Per Austrin; Jonah Brown-Cohen; Johan Håstad (Electron. Colloquium Comput. Complex., 2019)

Bounded Independence versus Symmetric Tests. - Ravi B. Boppana; Johan Håstad; Chin Ho Lee; Emanuele Viola (ACM Trans. Comput. Theory, 2019)

d-Galvin Families. - Johan Håstad; Guillaume Lagarde; Joseph Swernofsky (Electron. J. Comb., 2020)

The EATCS Award 2021 - Call for Nominations. - Marta Kwiatkowska; Éva Tardos; Johan Håstad (Bull. EATCS, 2020)

Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound. - Venkatesan Guruswami; Johan Håstad (IEEE Trans. Inf. Theory, 2021)

On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. - Johan Håstad; Kilian Risse (FOCS, 2022)

The EATCS Award 2023 - Call for Nominations. - Johan Håstad (Bull. EATCS, 2022)

The EATCS Award 2023 - Laudatio for Amos Fiat. - Johan Håstad (Bull. EATCS, 2023)

On small-depth Frege proofs for PHP. - Johan Håstad (Electron. Colloquium Comput. Complex., 2023)

A Logarithmic Approximation of Linearly-Ordered Colourings. - Johan Håstad; Björn Martinsson; Tamio-Vesa Nakajima; Stanislav Zivný (APPROX/RANDOM, 2024)

On the usefulness of Promises. - Per Austrin; Johan Håstad; Björn Martinsson (Electron. Colloquium Comput. Complex., 2025)