Johan Håstad

193 papers A* 47A 9B 1C 1Journal 120Unranked 14
YearRankTypeTitle / Venue / Authors
2026 A* conf
On the Usefulness of Promises.
SODA
Per Austrin, Johan Håstad, Björn Martinsson
2026 J jnl
Perfectly Satisfiable Systems of Linear Equations and Fixed Weight Solutions.
Electron. Colloquium Comput. Complex.
Johan Håstad
2025 J jnl
Efficiently finding small representations for LTFs.
Electron. Colloquium Comput. Complex.
Johan Håstad
2025 J jnl
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited.
SIAM J. Comput.
Johan Håstad, Kilian Risse
2025 J jnl
On Small-depth Frege Proofs for PHP.
TheoretiCS
Johan Håstad
2025 J jnl
On the Usefulness of Promises.
CoRR
Per Austrin, Johan Håstad, Björn Martinsson
2025 J jnl
On the usefulness of Promises.
Electron. Colloquium Comput. Complex.
Per Austrin, Johan Håstad, Björn Martinsson
2025 J jnl
Optimal Inapproximability with Universal Factor Graphs.
ACM Trans. Algorithms
Per Austrin, Jonah Brown-Cohen, Johan Håstad
2024 A conf
A Logarithmic Approximation of Linearly-Ordered Colourings.
APPROX/RANDOM
Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima, Stanislav Zivný
2024 J jnl
A logarithmic approximation of linearly-ordered colourings.
CoRR
Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima, Stanislav Zivný
2024 J jnl
On Small-depth Frege Proofs for PHP.
CoRR
Johan Håstad
2023 A* conf
On small-depth Frege proofs for PHP.
FOCS
Johan Håstad
2023 J jnl
On small-depth Frege proofs for PHP.
Electron. Colloquium Comput. Complex.
Johan Håstad
2023 J jnl
The EATCS Award 2023 - Laudatio for Amos Fiat.
Bull. EATCS
Johan Håstad
2022 A* conf
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited.
FOCS
Johan Håstad, Kilian Risse
2022 J jnl
On bounded depth proofs for Tseitin formulas on the grid; revisited.
CoRR
Johan Håstad, Kilian Risse
2022 J jnl
The EATCS Award 2023 - Call for Nominations.
Bull. EATCS
Johan Håstad
2021 J jnl
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound.
IEEE Trans. Inf. Theory
Venkatesan Guruswami, Johan Håstad
2021 A* conf
Explicit two-deletion codes with redundancy matching the existential bound.
SODA
Venkatesan Guruswami, Johan Håstad
2021 J jnl
On Small-depth Frege Proofs for Tseitin for Grids.
J. ACM
Johan Håstad
2021 A* conf
Optimal Inapproximability with Universal Factor Graphs.
SODA
Per Austrin, Jonah Brown-Cohen, Johan Håstad
2020 J jnl
Explicit two-deletion codes with redundancy matching the existential bound.
CoRR
Venkatesan Guruswami, Johan Håstad
2020 J jnl
The EATCS Award 2021 - Call for Nominations.
Bull. EATCS
Marta Kwiatkowska, Éva Tardos, Johan Håstad
2020 J jnl
d-Galvin Families.
Electron. J. Comb.
Johan Håstad, Guillaume Lagarde, Joseph Swernofsky
2019 J jnl
Bounded Independence versus Symmetric Tests.
ACM Trans. Comput. Theory
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
2019 — ch.
Following a tangent of proofs.
Providing Sound Foundations for Cryptography
Johan Håstad
2019 J jnl
Optimal Inapproximability with Universal Factor Graphs.
Electron. Colloquium Comput. Complex.
Per Austrin, Jonah Brown-Cohen, Johan Håstad
2018 A* conf
Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs.
FOCS
Johan Håstad
2017 J jnl
(2+ε)-Sat Is NP-hard.
SIAM J. Comput.
Per Austrin, Venkatesan Guruswami, Johan Håstad
2017 J jnl
An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
J. ACM
Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
2017 J jnl
An Improved Bound on the Fraction of Correctable Deletions.
IEEE Trans. Inf. Theory
Boris Bukh, Venkatesan Guruswami, Johan Håstad
2017 J jnl
Improved NP-Inapproximability for 2-Variable Linear Equations.
Theory Comput.
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
2017 A* conf
On Small-Depth Frege Proofs for Tseitin for Grids.
FOCS
Johan Håstad
2017 J jnl
On small-depth Frege proofs for Tseitin for grids.
Electron. Colloquium Comput. Complex.
Johan Håstad
2017 J jnl
On the Hardness of Approximating Balanced Homogenous 3-Lin.
Theory Comput.
Johan Håstad, Rajsekar Manokaran
2017 C conf
Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers.
PQCrypto
Martin Ekerå, Johan Håstad
2017 J jnl
Quantum algorithms for computing short discrete logarithms and factoring RSA integers.
CoRR
Martin Ekerå, Johan Håstad
2017 J jnl
Quantum algorithms for computing short discrete logarithms and factoring RSA integers.
IACR Cryptol. ePrint Arch.
Martin Ekerå, Johan Håstad
2017 J jnl
Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes.
SIAM J. Comput.
Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
2016 A* conf
An Average-Case Depth Hierarchy Theorem for Higher Depth.
FOCS
Johan Håstad
2016 J jnl
An average-case depth hierarchy theorem for higher depth.
Electron. Colloquium Comput. Complex.
Johan Håstad
2016 — conf
Bounded Independence vs. Moduli.
APPROX-RANDOM
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
2016 J jnl
Bounded independence vs. moduli.
Electron. Colloquium Comput. Complex.
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
2016 J jnl
The square lattice shuffle, correction.
Random Struct. Algorithms
Johan Håstad
2015 — conf
Improved NP-Inapproximability for 2-Variable Linear Equations.
APPROX-RANDOM
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
2015 J jnl
Making the Long Code Shorter.
SIAM J. Comput.
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2014 A* conf
(2 + epsilon)-Sat Is NP-Hard.
FOCS
Per Austrin, Johan Håstad, Venkatesan Guruswami
2014 J jnl
Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers.
SIAM J. Comput.
Johan Håstad, Bettina Just, J. C. Lagarias, Claus-Peter Schnorr
2014 — conf
On DNF Approximators for Monotone Boolean Functions.
ICALP (1)
Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan
2014 J jnl
On the Correlation of Parity and Small-Depth Circuits.
SIAM J. Comput.
Johan Håstad
2014 J jnl
On the NP-Hardness of Max-Not-2.
SIAM J. Comput.
Johan Håstad
2014 A* conf
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
STOC
Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
2013 J jnl
(2+ε)-SAT is NP-hard.
Electron. Colloquium Comput. Complex.
Per Austrin, Venkatesan Guruswami, Johan Håstad
2013 J jnl
On the Power of Many One-Bit Provers
CoRR
Per Austrin, Johan Håstad, Rafael Pass
2013 A conf
On the power of many one-bit provers.
ITCS
Per Austrin, Johan Håstad, Rafael Pass
2013 J jnl
On the usefulness of predicates.
ACM Trans. Comput. Theory
Per Austrin, Johan Håstad
2013 J jnl
Satisfying Degree-d Equations over GF[2]
Theory Comput.
Johan Håstad
2013 J jnl
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
CoRR
Venkatesan Guruswami, Johan Håstad, Prahladh Harsha, Srikanth Srinivasan, Girish Varma
2013 J jnl
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
Electron. Colloquium Comput. Complex.
Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
2013 J jnl
Towards an Optimal Separation of Space and Length in Resolution.
Theory Comput.
Jakob Nordström, Johan Håstad
2012 J jnl
Approximating Linear Threshold Predicates.
ACM Trans. Comput. Theory
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
2012 A* conf
Making the Long Code Shorter.
FOCS
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2012 — conf
On the NP-Hardness of Max-Not-2.
APPROX-RANDOM
Johan Håstad
2012 J jnl
On the Usefulness of Predicates
CoRR
Per Austrin, Johan Håstad
2012 A conf
On the Usefulness of Predicates.
CCC
Per Austrin, Johan Håstad
2012 J jnl
On the correlation of parity and small-depth circuits.
Electron. Colloquium Comput. Complex.
Johan Håstad
2012 J jnl
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451).
Dagstuhl Reports
Johan Håstad, Andrei A. Krokhin, Dániel Marx
2011 J jnl
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant.
SIAM J. Comput.
Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
2011 J jnl
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.
Electron. Colloquium Comput. Complex.
Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
2011 J jnl
Making the long code shorter, with applications to the Unique Games Conjecture
CoRR
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2011 J jnl
Making the long code shorter, with applications to the Unique Games Conjecture.
Electron. Colloquium Comput. Complex.
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2011 J jnl
On the List-Decodability of Random Linear Codes.
IEEE Trans. Inf. Theory
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
2011 J jnl
Randomly Supported Independence and Resistance.
SIAM J. Comput.
Per Austrin, Johan Håstad
2011 — conf
Satisfying Degree-d Equations over GF[2] n.
APPROX-RANDOM
Johan Håstad
2010 B conf
An Efficient Parallel Repetition Theorem.
TCC
Johan Håstad, Rafael Pass, Douglas Wikström, Krzysztof Pietrzak
2010 — conf
Approximating Linear Threshold Predicates.
APPROX-RANDOM
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
2010 J jnl
Approximating Linear Threshold Predicates.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
2010 J jnl
On the List-Decodability of Random Linear Codes
CoRR
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
2010 J jnl
On the List-Decodability of Random Linear Codes.
Electron. Colloquium Comput. Complex.
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
2010 A* conf
On the list-decodability of random linear codes.
STOC
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
2010 J jnl
Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword.
Comput. Complex.
Johan Håstad
2009 J jnl
On the Approximation Resistance of a Random Predicate.
Comput. Complex.
Johan Håstad
2009 A* conf
Randomly supported independence and resistance.
STOC
Per Austrin, Johan Håstad
2008 J jnl
Every 2-csp Allows Nontrivial Approximation.
Comput. Complex.
Johan Håstad
2008 J jnl
Practical Construction and Analysis of Pseudo-Randomness Primitives.
J. Cryptol.
Johan Håstad, Mats Näslund
2008 J jnl
Towards an Optimal Separation of Space and Length in Resolution
CoRR
Jakob Nordström, Johan Håstad
2008 J jnl
Towards an Optimal Separation of Space and Length in Resolution.
Electron. Colloquium Comput. Complex.
Jakob Nordström, Johan Håstad
2008 A* conf
Towards an optimal separation of space and length in resolution.
STOC
Jakob Nordström, Johan Håstad
2007 J jnl
A Smaller Sleeping Bag for a Baby Snake.
Discret. Comput. Geom.
Johan Håstad, Svante Linusson, Johan Wästlund
2007 — conf
On the Approximation Resistance of a Random Predicate.
APPROX-RANDOM
Johan Håstad
2007 J jnl
The Randomized Communication Complexity of Set Disjointness.
Theory Comput.
Johan Håstad, Avi Wigderson
2007 J jnl
The Security of the IAPM and IACBC Modes.
J. Cryptol.
Johan Håstad
2006 — conf
On Nontrivial Approximation of CSPs.
APPROX-RANDOM
Johan Håstad
2006 J jnl
The square lattice shuffle.
Random Struct. Algorithms
Johan Håstad
2005 A* conf
Every 2-CSP allows nontrivial approximation.
STOC
Johan Håstad
2005 J jnl
Query Efficient PCPs with Perfect Completeness.
Theory Comput.
Johan Håstad, Subhash Khot
2004 J jnl
On the advantage over a random assignment.
Random Struct. Algorithms
Johan Håstad, Srinivasan Venkatesh
2004 A* conf
Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes.
CRYPTO
Yevgeniy Dodis, Rosario Gennaro, Johan Håstad, Hugo Krawczyk, Tal Rabin
2004 J jnl
The security of all RSA and discrete log bits.
J. ACM
Johan Håstad, Mats Näslund
2003 J jnl
Fitting points on the real line and its application to RH mapping.
J. Algorithms
Johan Håstad, Lars Ivansson, Jens Lagergren
2003 A conf
Inapproximability Some history and some open problems.
CCC
Johan Håstad
2003 J jnl
Simple analysis of graph tests for linearity and PCP.
Random Struct. Algorithms
Johan Håstad, Avi Wigderson
2002 J jnl
Combinatorial bounds for list decoding.
IEEE Trans. Inf. Theory
Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman
2002 J jnl
Hardness of Approximate Hypergraph Coloring.
SIAM J. Comput.
Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2002 A* conf
On the advantage over a random assignment.
STOC
Johan Håstad, Srinivasan Venkatesh
2001 J jnl
A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p.
J. Algorithms
Gunnar Andersson, Lars Engebretsen, Johan Håstad
2001 J jnl
A Slight Sharpening of LMN.
J. Comput. Syst. Sci.
Johan Håstad
2001 J jnl
A Smaller Sleeping Bag for a Baby Snake.
Discret. Comput. Geom.
Johan Håstad, Svante Linusson, Johan Wästlund
2001 J jnl
Linear-Consistency Testing.
J. Comput. Syst. Sci.
Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan
2001 J jnl
On Lower Bounds for Selecting the Median.
SIAM J. Discret. Math.
Dorit Dor, Johan Håstad, Staffan Ulfberg, Uri Zwick
2001 A conf
Practical Construction and Analysis of Pseudo-Randomness Primitives.
ASIACRYPT
Johan Håstad, Mats Näslund
2001 A* conf
Query Efficient PCPs with Perfect Completeness.
FOCS
Johan Håstad, Subhash Khot
2001 A conf
Simple Analysis of Graph Tests for Linearity and PCP.
CCC
Johan Håstad, Avi Wigderson
2001 J jnl
Some optimal inapproximability results.
J. ACM
Johan Håstad
2000 A* conf
Funkspiel schemes: an alternative to conventional tamper resistance.
CCS
Johan Håstad, Jakob Jonsson, Ari Juels, Moti Yung
2000 A* conf
Hardness of Approximate Hypergraph Coloring.
FOCS
Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2000 J jnl
Hardness of approximate hypergraph coloring
Electron. Colloquium Comput. Complex.
Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2000 J jnl
On bounded occurrence constraint satisfaction.
Inf. Process. Lett.
Johan Håstad
2000 J jnl
Tight Bounds for Searching a Sorted Array of Strings.
SIAM J. Comput.
Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson
2000 A* conf
Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?
ICALP
Johan Håstad
1999 A* conf
A New Way to Use Semidefinite Programming with Applications to Linear Equations mod
SODA
Gunnar Andersson, Lars Engebretsen, Johan Håstad
1999 J jnl
A Pseudorandom Generator from any One-way Function.
SIAM J. Comput.
Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby
1999 J jnl
Linear Consistency Testing
Electron. Colloquium Comput. Complex.
Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan
1999 — conf
Linear Consistency Testing.
RANDOM-APPROX
Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan
1999 J jnl
On approximating CSP-B
Electron. Colloquium Comput. Complex.
Johan Håstad
1999 J jnl
Security of all RSA and Discrete Log Bits.
IACR Cryptol. ePrint Arch.
Johan Håstad, Mats Näslund
1999 J jnl
The Security of all RSA and Discrete Log Bits
Electron. Colloquium Comput. Complex.
Johan Håstad, Mats Näslund
1998 J jnl
Circuit Bottom Fan-In and Computational Power.
SIAM J. Comput.
Liming Cai, Jianer Chen, Johan Håstad
1998 A conf
Fitting Points on the Real Line and Its Application to RH Mapping.
ESA
Johan Håstad, Lars Ivansson, Jens Lagergren
1998 J jnl
Monotone Circuits for Connectivity Have Depth (log
SIAM J. Comput.
Mikael Goldmann, Johan Håstad
1998 J jnl
On the Complexity of Interactive Proofs with Bounded Communication.
Inf. Process. Lett.
Oded Goldreich, Johan Håstad
1998 — conf
Some Recent Strong Inapproximability Results.
SWAT
Johan Håstad
1998 A* conf
The Security of Individual RSA Bits.
FOCS
Johan Håstad, Mats Näslund
1998 J jnl
The Shrinkage Exponent of de Morgan Formulas is 2.
SIAM J. Comput.
Johan Håstad
1997 A conf
Circuit Bottom Fan-in and Computational Power.
CCC
Liming Cai, Jianer Chen, Johan Håstad
1997 J jnl
Clique is hard to approximate within n
Electron. Colloquium Comput. Complex.
Johan Håstad
1997 A* conf
Some Optimal Inapproximability Results.
STOC
Johan Håstad
1997 J jnl
Some optimal inapproximability results
Electron. Colloquium Comput. Complex.
Johan Håstad
1996 J jnl
Analysis of Backoff Protocols for Multiple Access Channels.
SIAM J. Comput.
Johan Håstad, Frank Thomson Leighton, Brian Rogoff
1996 A* conf
Clique is Hard to Approximate Within n
FOCS
Johan Håstad
1996 J jnl
Linearity testing in characteristic two.
IEEE Trans. Inf. Theory
Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan
1996 J jnl
On the Message Complexity of Interactive Proof Systems
Electron. Colloquium Comput. Complex.
Oded Goldreich, Johan Håstad
1996 A* conf
Testing of the Long Code and Hardness for Clique.
STOC
Johan Håstad
1995 A* conf
A tight lower bound for searching a sorted array.
STOC
Arne Andersson, Johan Håstad, Ola Petersson
1995 A* conf
Linearity Testing in Characteristic Two.
FOCS
Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan
1995 A* conf
Monotone circuits for connectivity have depth (log n)
STOC
Mikael Goldmann, Johan Håstad
1995 J jnl
On the Shrinkage Exponent for Read-Once Formulae.
Theor. Comput. Sci.
Johan Håstad, Alexander A. Razborov, Andrew Chi-Chih Yao
1995 J jnl
Top-Down Lower Bounds for Depth-Three Circuits.
Comput. Complex.
Johan Håstad, Stasys Jukna, Pavel Pudlák
1994 J jnl
On Average Time Hierarchies.
Inf. Process. Lett.
Mikael Goldmann, Per Grape, Johan Håstad
1994 J jnl
On the Size of Weights for Threshold Gates.
SIAM J. Discret. Math.
Johan Håstad
1994 J jnl
Optimal Depth, Very Small Size Circuits for Symmetric Functions in AC
Inf. Comput.
Johan Håstad, Ingo Wegener, Norbert Wurm, Sang-Zin Yi
1994 — conf
Recent Results in Hardness of Approximation.
SWAT
Johan Håstad
1994 J jnl
The Random Oracle Hypothesis Is False.
J. Comput. Syst. Sci.
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi
1994 A* conf
The complexity of searching a sorted array of strings.
STOC
Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson
1993 — conf
A Well-Characterized Approximation Problem.
ISTCS
Johan Håstad, Steven J. Phillips, Shmuel Safra
1993 J jnl
A Well-Characterized Approximation Problem.
Inf. Process. Lett.
Johan Håstad, Steven J. Phillips, Shmuel Safra
1993 J jnl
Addendum to "Simple Construction of Almost k-wise Independent Random Variables".
Random Struct. Algorithms
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta
1993 J jnl
The Discrete Logarithm Modulo a Composite Hides O(n) Bits.
J. Comput. Syst. Sci.
Johan Håstad, A. W. Schrift, Adi Shamir
1993 A* conf
The shrinkage exponent is 2
FOCS
Johan Håstad
1993 A* conf
Top-Down Lower Bounds for Depth 3 Circuits
FOCS
Johan Håstad, Stasys Jukna, Pavel Pudlák
1992 J jnl
A Simple Lower Bound for Monotone Clique Using a Communication Game.
Inf. Process. Lett.
Mikael Goldmann, Johan Håstad
1992 J jnl
Majority Gates VS. General Weighted Threshold Gates.
Comput. Complex.
Mikael Goldmann, Johan Håstad, Alexander A. Razborov
1992 — conf
Majority Gates vs. General Weighted Threshold Gates.
SCT
Mikael Goldmann, Johan Håstad, Alexander A. Razborov
1992 J jnl
Simple Construction of Almost k-wise Independent Random Variables.
Random Struct. Algorithms
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta
1991 J jnl
On the Power of Small-Depth Threshold Circuits.
Comput. Complex.
Johan Håstad, Mikael Goldmann
1991 J jnl
Relativized Perfect Zero Knowledge Is Not BPP
Inf. Comput.
William Aiello, Johan Håstad
1991 J jnl
Statistical Zero-Knowledge Languages can be Recognized in Two Rounds.
J. Comput. Syst. Sci.
William Aiello, Johan Håstad
1990 — conf
Composition of the Universal Relation.
Advances In Computational Complexity Theory
Johan Håstad, Avi Wigderson
1990 A* conf
On the Power of Small-Depth Threshold Circuits
FOCS
Johan Håstad, Mikael Goldmann
1990 J jnl
On the power of interaction.
Comb.
William Aiello, Shafi Goldwasser, Johan Håstad
1990 A* conf
Pseudo-Random Generators under Uniform Assumptions
STOC
Johan Håstad
1990 A* conf
Simple Constructions of Almost k-Wise Independent Random Variables
FOCS
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta
1990 J jnl
Tensor Rank is NP-Complete.
J. Algorithms
Johan Håstad
1989 A* conf
Fast Computation Using Faulty Hypercubes (Extended Abstract)
STOC
Johan Håstad, Frank Thomson Leighton, Mark Newman
1989 J jnl
Optimal bounds for decision problems on the CRCW PRAM.
J. ACM
Paul Beame, Johan Håstad
1989 J jnl
Polynomial Time Algorithms for Finding Integer Relations among Real Numbers.
SIAM J. Comput.
Johan Håstad, Bettina Just, J. C. Lagarias, Claus-Peter Schnorr
1989 A* conf
Tensor Rank is NP-Complete.
ICALP
Johan Håstad
1988 J jnl
Dual vectors and lower bounds for the nearest lattice point problem.
Comb.
Johan Håstad
1988 A* conf
Everything Provable is Provable in Zero-Knowledge.
CRYPTO
Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, Phillip Rogaway
1988 J jnl
Reconstructing Truncated Integer Variables Satisfying Linear Congruences.
SIAM J. Comput.
Alan M. Frieze, Johan Håstad, Ravi Kannan, J. C. Lagarias, Adi Shamir
1988 J jnl
Solving Simultaneous Modular Equations of Low Degree.
SIAM J. Comput.
Johan Håstad
1987 A* conf
Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract)
STOC
Johan Håstad, Frank Thomson Leighton, Brian Rogoff
1987 J jnl
Does co-NP Have Short Interactive Proofs?
Inf. Process. Lett.
Ravi B. Boppana, Johan Håstad, Stathis Zachos
1987 J jnl
One-Way Permutations in NC0.
Inf. Process. Lett.
Johan Håstad
1987 A* conf
Optimal Bounds for Decision Problems on the CRCW PRAM
STOC
Paul Beame, Johan Håstad
1987 A* conf
Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds
FOCS
William Aiello, Johan Håstad
1987 A* conf
Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract)
STOC
Johan Håstad, Frank Thomson Leighton, Mark Newman
1986 A* conf
Almost Optimal Lower Bounds for Small Depth Circuits
STOC
Johan Håstad
1986 A* conf
On the Power of Interaction
FOCS
William Aiello, Shafi Goldwasser, Johan Håstad
1986 A conf
Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers.
STACS
Johan Håstad, Bettina Helfrich, J. C. Lagarias, Claus-Peter Schnorr
1985 A* conf
On Using RSA with Low Exponent in a Public Key Network.
CRYPTO
Johan Håstad
1985 A* conf
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)
FOCS
Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky
1985 A* conf
The Cryptographic Security of Truncated Linearly Related Variables
STOC
Johan Håstad, Adi Shamir