Johan Torkel Håstad (; born 19 November 1960) is a Swedish theoretical computer scientist 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 explores the relationships between these classifications. A computational problem ...

. 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 tertiary education, post-secondary education and research institutions in most countries. Literally, ''professor'' derives from Latin ...

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

KTH Royal Institute of Technology KTH Royal Institute of Technology (), abbreviated KTH, is a Public university, public research university in Stockholm, Sweden. KTH conducts research and education in Institute of technology, engineering and technology and is Sweden's largest te ...

Stockholm Stockholm (; ) is the Capital city, capital and List of urban areas in Sweden by population, most populous city of Sweden, as well as the List of urban areas in the Nordic countries, largest urban area in the Nordic countries. Approximately ...

, 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 () 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 responsibility for promoting nat ...

since 2001. He received his B.S. in

Mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

Stockholm University Stockholm University (SU) () is a public university, 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, social ...

in 1981, his

M.S. A Master of Science (; abbreviated MS, M.S., MSc, M.Sc., SM, S.M., ScM or Sc.M.) is a master's degree. In contrast to the Master of Arts degree, the Master of Science degree is typically granted for studies in sciences, engineering and medicine ...

in Mathematics at

Uppsala University Uppsala University (UU) () 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 operation. Initially fou ...

in 1984 and his Ph.D. in Mathematics from

MIT The Massachusetts Institute of Technology (MIT) is a private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of modern technology and sc ...

in 1986. Håstad's thesis and 1994

concerned his work on lower bounds on the size of constant-depth Boolean circuits for the parity function. After Andrew Yao 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. It was first introduced by Johan Håstad to prove that AC0, AC0 Boolean circuits of depth ''k'' requ ...

, 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 ...

, 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 In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs ( proofs that can be checked by a randomiz ...

(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 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 IMU Abacus Medal (known before ...

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

Hebrew University of Jerusalem The Hebrew University of Jerusalem (HUJI; ) is an Israeli public university, public research university based in Jerusalem. Co-founded by Albert Einstein and Chaim Weizmann in July 1918, the public university officially opened on 1 April 1925. ...

. 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 Fellowship is an award and fellowship that recognises outstanding members of the Association for Computing Machinery (ACM). The title of ACM Fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals ...

in 2018 for "contributions in circuit complexity, approximability and inapproximability, and foundations of

pseudorandomness A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Pseudorandom number generators are often used in computer programming, as tradi ...

". In 2018 he received the Knuth Prize "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 Parallel computing is a type of computing, computation in which many calculations or Process (computing), processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. ...

, 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 Academic staff of the KTH Royal Institute of Technology Members of the Royal Swedish Academy of Sciences Massachusetts Institute of Technology School of Science alumni Fellows of the American Mathematical Society 2018 fellows of the Association for Computing Machinery International Mathematical Olympiad participants Theoretical computer scientists