Johan Håstad
Encyclopedia
Johan Torkel Håstad is a Swedish
theoretical computer scientist
most known for his work on computational complexity theory
. He was the recipient of the Gödel Prize
in 1994 and 2011 and the ACM
Doctoral Dissertation Award in 1986, among other prizes. He is a professor
in theoretical computer science
at the Royal Institute of Technology
in Stockholm
, Sweden since 1992. He is a member of the Royal Swedish Academy of Sciences
since 2001.
He received his B.S.
in Mathematics
at Stockholm University
in 1981, his M.S.
in Mathematics at Uppsala University
in 1984 and his Ph.D.
in Mathematics from MIT
in 1986.
Håstad's thesis and Gödel Prize
(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
, which became an important technical tool in Boolean function complexity.
He is also going to receive the 2011 Godel Prize for his work on optimal inapproximability results.
Sweden
Sweden , officially the Kingdom of Sweden , is a Nordic country on the Scandinavian Peninsula in Northern Europe. Sweden borders with Norway and Finland and is connected to Denmark by a bridge-tunnel across the Öresund....
theoretical computer scientist
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
most known for his work on computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. He was the recipient of the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
in 1994 and 2011 and the ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
Doctoral Dissertation Award in 1986, among other prizes. He is a professor
Professor
A professor is a scholarly teacher; the precise meaning of the term varies by country. Literally, professor derives from Latin as a "person who professes" being usually an expert in arts or sciences; a teacher of high rank...
in theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
at the Royal Institute of Technology
Royal Institute of Technology
The Royal Institute of Technology is a university in Stockholm, Sweden. KTH was founded in 1827 as Sweden's first polytechnic and is one of Scandinavia's largest institutions of higher education in technology. KTH accounts for one-third of Sweden’s technical research and engineering education...
in Stockholm
Stockholm
Stockholm is the capital and the largest city of Sweden and constitutes the most populated urban area in Scandinavia. Stockholm is the most populous city in Sweden, with a population of 851,155 in the municipality , 1.37 million in the urban area , and around 2.1 million in the metropolitan area...
, Sweden since 1992. He is a member of the Royal Swedish Academy of Sciences
Royal Swedish Academy of Sciences
The Royal Swedish Academy of Sciences or Kungliga Vetenskapsakademien is one of the Royal Academies of Sweden. The Academy is an independent, non-governmental scientific organization which acts to promote the sciences, primarily the natural sciences and mathematics.The Academy was founded on 2...
since 2001.
He received his B.S.
Bachelor of Science
A Bachelor of Science is an undergraduate academic degree awarded for completed courses that generally last three to five years .-Australia:In Australia, the BSc is a 3 year degree, offered from 1st year on...
in Mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
at Stockholm University
Stockholm University
Stockholm University is a state university in Stockholm, Sweden. It has over 28,000 students at four faculties, making it one of the largest universities in Scandinavia. The institution is also frequently regarded as one of the top 100 universities in the world...
in 1981, his M.S.
Master of Science
A Master of Science is a postgraduate academic master's degree awarded by universities in many countries. The degree is typically studied for in the sciences including the social sciences.-Brazil, Argentina and Uruguay:...
in Mathematics at Uppsala University
Uppsala University
Uppsala University is a research university in Uppsala, Sweden, and is the oldest university in Scandinavia, founded in 1477. It consistently ranks among the best universities in Northern Europe in international rankings and is generally considered one of the most prestigious institutions of...
in 1984 and his Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
in Mathematics from MIT
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
in 1986.
Håstad's thesis and Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
(1994) concerned his work on lower bounds on the size of constant-depth Boolean circuits for the parity function
Parity function
In Boolean algebra, a parity function is a Boolean function whose value is 1 if the input vector has an odd number of ones.The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions.-Definition:...
. After Andrew Yao
Andrew Yao
Andrew Chi-Chih Yao is a prominent computer scientist and computational theorist. Yao used the minimax theorem to prove what is now known as Yao's Principle.Yao was born in Shanghai, China...
proved that such circuits require exponential size, Håstad proved nearly optimal lower bounds on the necessary size through his switching lemma
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....
, which became an important technical tool in Boolean function complexity.
He is also going to receive the 2011 Godel Prize for his work on optimal inapproximability results.