Johan Håstad

Johan Torkel Håstad, född 19 november 1960, är en svensk matematiker, forskare och professor inom teoretisk datalogi.

Håstad visade redan som gymnasist prov på matematisk talang genom goda resultat i matematikolympiaden, där han är en av endast sex svenskar som fått en guldmedalj.^[1] Håstad studerade inledningsvis vid Stockholms universitet där han 1981 tog högskoleexamen i matematik, och därefter en licentiatexamen i matematik vid Uppsala universitet 1984. 1986 blev han Ph.D. i matematik vid Massachusetts Institute of Technology på en avhandling^[2] om "Computational limitations of small-depth circuits". Han stannade där som postdok till 1987, och anställdes 1988 som högskolelektor och antogs som docent i datalogi vid Kungliga Tekniska högskolan. År 1992 utnämndes han till professor i teoretisk datalogi.^[3]

Hans forskningsområde är teoretisk datalogi, bland annat komplexitetsteori och kryptografi. Inom det senare området är han bland annat känd för Håstads attack.

Håstad invaldes 2001 som ledamot av Kungliga Vetenskapsakademien, i klassen för matematik. Han tilldelades Gödelpriset både 1994 och 2011.^[4]

Utmärkelser

1994 – Gödelpriset^[4]^[5] för "the first non-trivial bounds for unbounded fan-in circuit depth that are asymptotically optimal for any function in NP - Almost optimal lower bounds for small depth circuits, Advances in Computing Research 5 (1989), 143-170
2011 – Gödelpriset^[6]^[7] för "a landmark paper in computational complexity - Some optimal inapproximability results, Journal of the ACM, 48: 798--859, 2001"
2018 – Knuth-priset för "en serie omvälvande bidrag bland annat till områdena kryptering, optimering, parallella beräkningar och komplexitetsteori"^[8]

^ ”International Mathematical Olympiad”. International Mathematical Olympiad. http://www.imo-official.org/country_individual_r.aspx?code=SWE. Läst 7 september 2013.
^ Håstad, Johan Torkel (1987) (på engelska). Computational limitations of small-depth circuits. ACM doctoral dissertation award, 99-0520147-5 ; 1986. Cambridge, Mass.: MIT Press. Libris 4738741. ISBN 0-262-08167-9
^ Johan Håstads CV, version december 2008
^ [a b] ”Gödel Prize”. ACM Special Interest Group on Algorithms and Computation Theory. Arkiverad från originalet den 16 juli 2010. https://web.archive.org/web/20100716200535/http://www.sigact.org/prizes/godel/. Läst 21 maj 2011.
^ ”Gödel Prize - 1994”. EATCS - European Association for Theoretical Computer Science. http://eatcs.org/index.php/component/content/article/514. Läst 25 december 2019.
^ ”Gödel Prize (together with ACM SIGACT)”. European Association for Theoretical Computer Science. http://eatcs.org/index.php/goedel-prize. Läst 25 december 2019.
^ ”2011 Gödel Prize”. EATCS - European Association for Theoretical Computer Science. http://eatcs.org/images/awards/goedel11.pdf. Läst 25 december 2019.
^ Jan Tångring (17 augusti 2018). ”Knuth-priset till framstående svensk datalog”. Elektroniktidningen. http://etn.se/index.php/nyheter/64915-knuth-priset-till-framstaende-svensk-datalog.html. Läst 25 december 2019.