Hastad Johan

Johan Håstad is a Full Professor in the Department of Computer Science at the Royal Institute of Technology (KTH), Sweden, since 1992. Previously, he held academic positions at KTH and the Massachusetts Institute of Technology (MIT) as a Postdoctoral Fellow (1986-1987). His work lies at the intersection of theoretical computer science and mathematics, with foundational contributions to computational complexity theory, cryptography, and approximation algorithms.

• Ph.D. in Mathematics from MIT (1986)
• Member of the Royal Swedish Academy of Sciences (2001)
• Knuth Prize laureate (2018) for breakthroughs in optimization, cryptography, parallel computing, and complexity theory

Research Focus:
Johan Håstad's research has fundamentally shaped computational complexity theory, particularly in understanding the limits of efficient computation and approximation. His work on probabilistically checkable proofs (PCPs) and hardness of approximation has had a profound impact on theoretical computer science, influencing areas like cryptography and parallel computing. He is known for developing Håstad's switching lemma and establishing strong inapproximability results for NP-hard problems.

Scientific Recognition:

• ACM Doctoral Dissertation Award (1986)
• Gödel Prize (1994, 2011)
• Chester Carlson Research Prize (1990)
• Göran Gustafsson Prize (1999)
• Knuth Prize (2018)