Johan Håstad

E22525

computer scientist human mathematician theoretical computer scientist

Johan Håstad is a Swedish theoretical computer scientist renowned for his groundbreaking work in computational complexity theory, particularly optimal inapproximability results and contributions to the PCP theorem.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

AI illustration

All labels observed (1)

Label	Occurrences
Johan Håstad canonical	5

How this entity was disambiguated

This entity first appeared as the object of triple T143819 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Johan Håstad
Context triple: [Shafi Goldwasser, coAuthor, Johan Håstad]

A. Manuel Blum
Manuel Blum is a Venezuelan-American computer scientist and Turing Award laureate renowned for his foundational contributions to computational complexity theory and cryptography.
B. Oded Goldreich
Oded Goldreich is an Israeli computer scientist renowned for his foundational contributions to cryptography, computational complexity, and the theory of pseudorandomness.
C. Michael Sipser
Michael Sipser is an American theoretical computer scientist known for his influential work in computational complexity theory and for authoring a widely used textbook on the theory of computation.
D. Silvio Micali
Silvio Micali is an Italian computer scientist renowned for his foundational contributions to cryptography, zero-knowledge proofs, and secure protocols.
E. Shafi Goldwasser
Shafi Goldwasser is an Israeli-American computer scientist renowned for her foundational contributions to cryptography and computational complexity theory.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Johan Håstad
Target entity description: Johan Håstad is a Swedish theoretical computer scientist renowned for his groundbreaking work in computational complexity theory, particularly optimal inapproximability results and contributions to the PCP theorem.

A. Manuel Blum
Manuel Blum is a Venezuelan-American computer scientist and Turing Award laureate renowned for his foundational contributions to computational complexity theory and cryptography.
B. Oded Goldreich
Oded Goldreich is an Israeli computer scientist renowned for his foundational contributions to cryptography, computational complexity, and the theory of pseudorandomness.
C. Michael Sipser
Michael Sipser is an American theoretical computer scientist known for his influential work in computational complexity theory and for authoring a widely used textbook on the theory of computation.
D. Silvio Micali
Silvio Micali is an Italian computer scientist renowned for his foundational contributions to cryptography, zero-knowledge proofs, and secure protocols.
E. Shafi Goldwasser
Shafi Goldwasser is an Israeli-American computer scientist renowned for her foundational contributions to cryptography and computational complexity theory.
F. None of above. chosen

Statements (48)

Predicate	Object
instanceOf	computer scientist ⓘ human ⓘ mathematician ⓘ theoretical computer scientist ⓘ
academicDegree	PhD in computer science ⓘ
affiliation	School of Computer Science and Communication at KTH ⓘ linked to: KTH Royal Institute of Technology
awardReceived	ACM Paris Kanellakis Theory and Practice Award ⓘ linked to: Paris Kanellakis Theory and Practice Award ACM SIGACT Gödel Prize ⓘ linked to: Gödel Prize Gödel Prize ⓘ Gödel Prize 1994 ⓘ linked to: Gödel Prize Gödel Prize 2011 ⓘ Royal Swedish Academy of Engineering Sciences Gold Medal ⓘ linked to: Royal Swedish Academy of Engineering Sciences Royal Swedish Academy of Sciences prize in mathematics ⓘ linked to: Crafoord Prize
citizenship	Sweden ⓘ
countryOfCitizenship	Sweden ⓘ
doctoralAdvisor	Jeffrey D. Ullman ⓘ
educatedAt	KTH Royal Institute of Technology ⓘ Massachusetts Institute of Technology ⓘ
employer	KTH Royal Institute of Technology ⓘ
fieldOfWork	approximation algorithms ⓘ computational complexity theory ⓘ probabilistically checkable proofs ⓘ theoretical computer science ⓘ
gender	male ⓘ
influenced	development of PCP-based inapproximability ⓘ research on hardness of approximation ⓘ
knownFor	Håstad’s switching lemma ⓘ PCP theorem ⓘ hardness of approximation for Max-Cut ⓘ hardness of approximation for Max-E3-SAT ⓘ hardness of approximation for set cover ⓘ hardness of approximation for vertex cover ⓘ optimal inapproximability results ⓘ results on bounded-depth Boolean circuits ⓘ results on small-depth circuits ⓘ
memberOf	Royal Swedish Academy of Engineering Sciences ⓘ Royal Swedish Academy of Sciences ⓘ
nativeLanguage	Swedish ⓘ
notableConcept	Håstad’s optimal inapproximability bounds ⓘ Håstad’s switching lemma ⓘ
notableWork	“Almost optimal lower bounds for small depth circuits” ⓘ “Clique is hard to approximate within n^{1−ε}” ⓘ “Inapproximability results for SAT and other problems” ⓘ “Some optimal inapproximability results” ⓘ linked to: Interactive Proofs and the Hardness of Approximating Cliques
placeOfWork	Stockholm ⓘ
positionHeld	professor of theoretical computer science ⓘ
thesisTitle	Computational limitations of small-depth circuits ⓘ
workplace	KTH Royal Institute of Technology ⓘ