Johan Torkel Håstad (; born 19 November 1960) is a

Swedish Swedish or ' may refer to: Anything from or related to Sweden, a country in Northern Europe. Or, specifically: * Swedish language, a North Germanic language spoken primarily in Sweden and Finland ** Swedish alphabet, the official alphabet used by ...

theoretical computer scientist computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the th ...

most known for his work on

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

. He was the recipient of the

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

in 1994 and 2011 and the ACM Doctoral Dissertation Award in 1986, among other prizes. He has been a

professor Professor (commonly abbreviated as Prof.) is an Academy, academic rank at university, universities and other post-secondary education and research institutions in most countries. Literally, ''professor'' derives from Latin as a "person who pr ...

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

KTH Royal Institute of Technology The KTH Royal Institute of Technology ( sv, Kungliga Tekniska högskolan, lit=Royal Institute of Technology), abbreviated KTH, is a public research university in Stockholm, Sweden. KTH conducts research and education in engineering and technolo ...

Stockholm Stockholm () is the Capital city, capital and List of urban areas in Sweden by population, largest city of Sweden as well as the List of urban areas in the Nordic countries, largest urban area in Scandinavia. Approximately 980,000 people liv ...

, Sweden since 1988, becoming a full professor in 1992. He is a member of the

Royal Swedish Academy of Sciences The Royal Swedish Academy of Sciences ( sv, Kungliga Vetenskapsakademien) is one of the Swedish Royal Academies, royal academies of Sweden. Founded on 2 June 1739, it is an independent, non-governmental scientific organization that takes special ...

since 2001. He received his

B.S. A Bachelor of Science (BS, BSc, SB, or ScB; from the Latin ') is a bachelor's degree awarded for programs that generally last three to five years. The first university to admit a student to the degree of Bachelor of Science was the University ...

Mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

Stockholm University Stockholm University ( sv, Stockholms universitet) is a public research university in Stockholm, Sweden, founded as a college in 1878, with university status since 1960. With over 33,000 students at four different faculties: law, humanities, so ...

in 1981, his

M.S. A Master of Science ( la, Magisterii Scientiae; abbreviated MS, M.S., MSc, M.Sc., SM, S.M., ScM or Sc.M.) is a master's degree in the field of science awarded by universities in many countries or a person holding such a degree. In contrast to ...

in Mathematics at

Uppsala University Uppsala University ( sv, Uppsala universitet) is a public university, public research university in Uppsala, Sweden. Founded in 1477, it is the List of universities in Sweden, oldest university in Sweden and the Nordic countries still in opera ...

in 1984 and his

Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...

in Mathematics from

MIT The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...

in 1986. Håstad's thesis and 1994

concerned his work on

lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an element ...

s on the size of constant-depth

Boolean circuits In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input ...

for the

parity function In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function. The parity function is notable for its ...

. After

Andrew Yao Andrew Chi-Chih Yao (; born December 24, 1946) is a Chinese computer scientist and computational theorist. He is currently a professor and the dean of Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. Yao use ...

proved that such circuits require exponential size, Håstad proved nearly optimal lower bounds on the necessary size through his

switching lemma In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. Using the switching lemma, showed that Boolean circuits of depth ''k'' in which only AND, OR, and N ...

, which became an important technical tool in

circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...

with applications to

learnability Learnability is a quality of products and interfaces that allows users to quickly become familiar with them and able to make good use of all their features and capabilities. Software testing In software testing learnability, according to ISO/IEC 9 ...

, the IP hierarchy, and proof systems. He also received the 2011 Gödel Prize for his work on optimal inapproximability results. In particular, he improved the PCP theorem (which won the same prize in 2001) to give a probabilistic verifier for NP problems which reads only three bits. Further, he used these results to prove results in

hardness of approximation In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Scope Hardness of approximation complements the study of approximation algorithms by prov ...

. In 1998 Håstad was an Invited Speaker of the

International Congress of Mathematicians The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU). The Fields Medals, the Nevanlinna Prize (to be rename ...

in Berlin. In 1999 he was an Erdős Lecturer at the

Hebrew University of Jerusalem The Hebrew University of Jerusalem (HUJI; he, הַאוּנִיבֶרְסִיטָה הַעִבְרִית בִּירוּשָׁלַיִם) is a public research university based in Jerusalem, Israel. Co-founded by Albert Einstein and Dr. Chaim Weiz ...

. In 2012, he became a fellow of the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

. He was elected as an

ACM Fellow ACM or A.C.M. may refer to: Aviation * AGM-129 ACM, 1990–2012 USAF cruise missile * Air chief marshal * Air combat manoeuvring or dogfighting * Air cycle machine * Arica Airport (Colombia) (IATA: ACM), in Arica, Amazonas, Colombia Computing ...

in 2018 for "contributions in circuit complexity, approximability and inapproximability, and foundations of pseudorandomness". In 2018 he received the

Knuth Prize The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth. History The Knuth Prize has been awarded since 1996 and includes an award of US ...

"for his long and sustained record of milestone breakthroughs at the foundations of computer science, with huge impact on many areas including optimization, cryptography, parallel computing, and complexity theory."

References

External links

Johan Håstad's home page
* {{DEFAULTSORT:Hastad, Johan 1960 births Living people Swedish computer scientists 20th-century Swedish mathematicians 21st-century Swedish mathematicians Gödel Prize laureates Knuth Prize laureates Uppsala University alumni Stockholm University alumni KTH Royal Institute of Technology faculty Members of the Royal Swedish Academy of Sciences Massachusetts Institute of Technology School of Science alumni Fellows of the American Mathematical Society Fellows of the Association for Computing Machinery International Mathematical Olympiad participants Theoretical computer scientists