Concepedia

Johan Håstad

JH

86

Publications

9.5K

Citations

40

H-Index

1985

Active since

Affiliations

KTH Royal Institute of Technology(Current)

Massachusetts Institute of Technology

Johan Håstad is an author at KTH Royal Institute of Technology specializing in engineering, computational complexity, and computer science.

Top concepts

EngineeringComputational ComplexityComputer ScienceDiscrete MathematicsCombinatorial OptimizationMathematical ProgrammingApproximation TheoryTheory Of ComputingFormal MethodsAutomated Reasoning

Publications per year

1985–2021

86

Publications

86

A Pseudorandom Generator from any One-way Function

Johan Håstad, Russell Impagliazzo, Leonid A. Levin et al. · SIAM Journal on Computing · 1999 · 1.7K citations

Engineering, Pseudo-random Sequence, Pseudorandom Generators +12

Clique is hard to approximate within n1−ε

Johan Håstad · Acta Mathematica · 1999 · 1.4K citations · Full text

Almost optimal lower bounds for small depth circuits

Johan Håstad · 1986 · 624 citations

Circuit Complexity, Theory Of Computing, Computational Science +12

Tensor rank is NP-complete

Johan Håstad · Journal of Algorithms · 1990 · 586 citations

Tensor Rank, Low-rank Approximation, Matrix Factorization

Simple Constructions of Almost k‐wise Independent Random Variables

Noga Alon, Oded Goldreich, Johan Håstad et al. · Random Structures and Algorithms · 1992 · 556 citations

K Bits, Engineering, Information Theory +13

Rows per page

1–5 of 86