Johan Håstad

Q: What Schools Are Affiliated With Johan Håstad

Johan Håstad is affiliated with the following schools: Stockholm University, Uppsala University, Massachusetts Institute of Technology, KTH Royal Institute of Technology

Johan Håstad's AcademicInfluence.com Rankings

Johan Håstad

Computer Science

#597

World Rank

#617

Historical Rank

Theoretical Computer Science

#21

World Rank

#21

Historical Rank

Database

#1869

World Rank

#1960

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Johan Håstad's Degrees

PhD Computer Science KTH Royal Institute of Technology

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Johan Håstad Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Johan Torkel Håstad is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation Award in 1986, among other prizes. He has been a professor in theoretical computer science at KTH Royal Institute of Technology in Stockholm, Sweden since 1988, becoming a full professor in 1992. He is a member of the Royal Swedish Academy of Sciences since 2001.

(See a Problem?)

Johan Håstad's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Some optimal inapproximability results (2001) (1775)
A Pseudorandom Generator from any One-way Function (1999) (1534)
Clique is hard to approximate withinn1−ε (1999) (1323)
Almost optimal lower bounds for small depth circuits (1986) (807)
Tensor Rank is NP-Complete (1989) (593)
Computational limitations of small-depth circuits (1987) (545)
Clique is hard to approximate within n/sup 1-/spl epsiv// (1996) (433)
Simple construction of almost k-wise independent random variables (1990) (422)
Does co-NP Have Short Interactive Proofs? (1987) (382)
The bit extraction problem or t-resilient functions (1985) (370)
Clique is hard to approximate within n 1-C (1996) (327)
Simple Constructions of Almost k -wise Independent Random Variables (2002) (309)
On the power of small-depth threshold circuits (1990) (301)
Majority gates vs. general weighted threshold gates (1992) (238)
Everything Provable is Provable in Zero-Knowledge (1990) (237)
Analysis of backoff protocols for multiple access channels (1987) (232)
Clique is hard to approximate within n1-epsilon (1996) (202)
Solving Simultaneous Modular Equations of Low Degree (1988) (198)
Linearity testing in characteristic two (1995) (188)
Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes (2004) (185)
Optimal bounds for decision problems on the CRCW PRAM (1987) (177)
Some optimal inapproximability results (1997) (160)
Pseudo-random generators under uniform assumptions (1990) (144)
On the Size of Weights for Threshold Gates (1994) (137)
Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers (1989) (133)
On Using RSA with Low Exponent in a Public Key Network (1985) (132)
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) (1985) (122)
Statistical Zero-Knowledge Languages can be Recognized in Two Rounds (1991) (122)
Reconstructing Truncated Integer Variables Satisfying Linear Congruences (1988) (119)
Reconfiguring a hypercube in the presence of faults (1987) (116)
The Shrinkage Exponent of de Morgan Formulas is 2 (1998) (111)
The Randomized Communication Complexity of Set Disjointness (2007) (101)
Fast computation using faulty hypercubes (1989) (100)
Combinatorial bounds for list decoding (2002) (99)
Simple analysis of graph tests for linearity and PCP (2001) (88)
On the Complexity of Interactive Proofs with Bounded Communication (1998) (85)
The Discrete Logarithm Modulo a Composite Hides O(n) Bits (1993) (80)
Hardness of approximate hypergraph coloring (2000) (76)
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant (2011) (74)
On the Correlation of Parity and Small-Depth Circuits (2014) (74)
Optimal bounds for decision problems on the CRCW PRAM (1989) (74)
Making the Long Code Shorter (2012) (68)
Testing of the long code and hardness for clique (1996) (57)
On the advantage over a random assignment (2002) (57)
An Efficient Parallel Repetition Theorem (2010) (56)
On the List-Decodability of Random Linear Codes (2010) (55)
Perfect zero-knowledge languages can be recognized in two rounds (1987) (54)
The Random Oracle Hypothesis Is False (1994) (51)
Composition of the Universal Relation (1990) (51)
The cryptographic security of truncated linearly related variables (1985) (51)
The security of individual RSA bits (1998) (48)
An Improved Bound on the Fraction of Correctable Deletions (2015) (47)
The security of all RSA and discrete log bits (2004) (46)
Every 2-csp Allows Nontrivial Approximation (2005) (45)
Randomly supported independence and resistance (2009) (44)
(2+ε)-Sat Is NP-hard (2014) (43)
Query efficient PCPs with perfect completeness (2001) (43)
On the Usefulness of Predicates (2012) (42)
A new way to use semidefinite programming with applications to linear equations mod p (2001) (42)
A well-characterized approximation problem (1993) (39)
Towards an optimal separation of space and length in resolution (2008) (39)
A Simple Lower Bound for Monotone Clique Using a Communication Game (1992) (37)
Fitting Points on the Real Line and Its Application to RH Mapping (1998) (33)
Top-down lower bounds for depth-three circuits (1995) (33)
On bounded occurrence constraint satisfaction (2000) (28)
The shrinkage exponent is 2 (1993) (28)
On the Approximation Resistance of a Random Predicate (2007) (27)
On the power of interaction (1986) (27)
Dual vectors and lower bounds for the nearest lattice point problem (1988) (27)
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes (2013) (26)
One-Way Permutations in NC0 (1987) (26)
Making the long code shorter, with applications to the Unique Games Conjecture (2011) (25)
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound (2020) (25)
A Slight Sharpening of LMN (2001) (23)
On Small-Depth Frege Proofs for Tseitin for Grids (2017) (23)
Addendum to "Simple Construction of Almost k-wise Independent Random Variables" (1993) (23)
On the NP-Hardness of Max-Not-2 (2014) (22)
Top-down lower bounds for depth 3 circuits (1993) (20)
On the efficient approximability of constraint satisfaction problems (2007) (20)
Funkspiel schemes: an alternative to conventional tamper resistance (2000) (20)
The square lattice shuffle (2006) (19)
Fast Computation Using Faulty Hypercubes (Extended Abstract) (1989) (18)
Optimal Depth, Very Small Size Circuits for Symmetric Functions in AC0 (1994) (18)
Tight Bounds for Searching a Sorted Array of Strings (2000) (16)
On Average Time Hierarchies (1994) (15)
Practical Construction and Analysis of Pseudo-Randomness Primitives (2001) (15)
ONEWAY PERMUTATIONS IN NC 0 (1987) (14)
Monotone Circuits for Connectivity Have Depth (log n)2-o(1) (1998) (14)
Linear Consistency Testing (1999) (14)
On the Shrinkage Exponent for Read-Once Formulae (1995) (13)
On Lower Bounds for Selecting the Median (2001) (13)
Approximating Linear Threshold Predicates (2010) (12)
Quantum algorithms for computing short discrete logarithms and factoring RSA integers (2017) (11)
Simultaneously good bases of a lattice and its reciprocal lattice (1990) (9)
The complexity of searching a sorted array of strings (1994) (9)
(2 + epsilon)-Sat Is NP-Hard (2014) (9)
Key Feedback Mode : a Keystream Generator with Provable Security (2000) (9)
Circuit bottom fan-in and computational power (1997) (8)
Satisfying Degree-d Equations over GF[2] n (2011) (8)
Relativized Perfect Zero Knowledge Is Not BPP (1991) (8)
Simultaneous Diophantine approximation of rationals by rationals (1986) (7)
Improved NP-Inapproximability for 2-Variable Linear Equations (2017) (6)
Improved Analysis of the BMGL Keystream Generator (2001) (6)
The Security of the IAPM and IACBC Modes (2007) (6)
Bounded Independence versus Symmetric Tests (2019) (6)
Monotone circuits for connectivity have depth (log n)2-o(1) (extended abstract) (1995) (5)
A Smaller Sleeping Bag for a Baby Snake (2001) (5)
Complexity Theory, Proofs and Approximation (2005) (5)
On DNF Approximators for Monotone Boolean Functions (2014) (5)
An Average-Case Depth Hierarchy Theorem for Higher Depth (2016) (5)
A tight lower bound for searching a sorted array (1995) (4)
Satisfying Degree D Equations over Gf [2] (2011) (4)
Recent Results in Hardness of Approximation (1994) (4)
Optimal Inapproximability with Universal Factor Graphs (2021) (3)
The square lattice shuffle, correction (2016) (3)
Inapproximability - some history and some open problems (2003) (3)
Practical Evaluation of Revocation Schemes (2004) (2)
Message integrity of IAPM and IACBC (2001) (2)
On the Message Complexity of Interactive Proof Systems (1996) (2)
Verification of the Session Management Protocol (2)
On the power of many one-bit provers (2013) (1)
Some Recent Strong Inapproximability Results (1998) (1)
Bounded independence vs. moduli (2016) (1)
Improved NP-Inapproximability for 2-Variable Linear Equations (2015) (1)
Satisfying Degree-d Equations over GF[2]n (2013) (1)
BMGL : Synchronous Keystream Generator with Provable Security ( Revision 1 ) (2001) (1)
On the Hardness of Approximating Balanced Homogenous 3-Lin (2017) (1)
Practical Construction and Analysis of Pseudo-Randomness Primitives (2008) (1)
On the distribution of multiplicative translates of sets of residues (mod p) (1994) (0)
( 2 + ε )-S AT is NP-hard ∗ (2014) (0)
On approximating CSP-B (1999) (0)
The Number Field Sieve an Integer Factorization Algorithm the Number Field Sieve an Integer Factorization Algorithm (0)
On approximating NP-hard optimization problems. (1998) (0)
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited (2022) (0)
The EATCS Award 2021 - Call for Nominations (2020) (0)
Inference of buffer queue times in data processing systems using Gaussian Processes (2017) (0)
Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? (2000) (0)
Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs (2018) (0)
On Nontrivial Approximation of CSPs (2006) (0)
Special Issue “Conference on Computational Complexity 2009” Guest Editor’s Foreword (2010) (0)
?J USING RSA WITH LOW EXPONENT IN A PUBLIC KEY NETWORM (2002) (0)
Following a tangent of proofs (2019) (0)
A Smaller Sleeping Bag for a Baby Snake (2007) (0)

This paper list is powered by the following services:

Other Resources About Johan Håstad

What Schools Are Affiliated With Johan Håstad?

Johan Håstad is affiliated with the following schools:

Johan Håstad's Academic­Influence.com Rankings

Johan Håstad's Degrees

Similar Degrees You Can Earn

Why Is Johan Håstad Influential?

Johan Håstad's Published Works

Published Works

Other Resources About Johan Håstad

What Schools Are Affiliated With Johan Håstad?

Johan Håstad's AcademicInfluence.com Rankings