Leonid Levin
| Leonid Anatolievich Levin | |
|---|---|
| File:LeonidLevin2010.jpg | |
| Born | November 2, 1948 Dnipropetrovsk, Ukrainian SSR, Soviet Union |
| Fields | Computer Science |
| Institutions | Boston University |
| Alma mater | Moscow University Massachusetts Institute of Technology |
| Doctoral advisor | Andrey Kolmogorov, Albert R. Meyer |
| Known for | research in complexity, randomness, information |
| Notable awards | Knuth Prize (2012) |
Leonid Anatolievich Levin (le-oh-NEED LE-vin; Russian: Леони́д Анато́льевич Ле́вин; Ukrainian: Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American computer scientist.
Contents
Biography
He obtained his master's degree at Moscow University in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972.[1][2] After researching in algorithmic problems of information theory at the Moscow Institute of Information Transmission of the National Academy of Sciences in 1972-1973, and a position as Senior Research Scientist at the Moscow National Research Institute of Integrated Automation for the Oil/Gas Industry in 1973-1977, he emigrated to the U.S. in 1978 and also earned a Ph.D. at the Massachusetts Institute of Technology (MIT) in 1979.[1] His advisor at MIT was Albert R. Meyer.
He is well known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity,[3] foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory.
His life is described in a chapter of the book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.[4]
Levin and Stephen Cook independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook-Levin Theorem, was a basis for one of the seven Millennium Prize Problems declared by the Clay Mathematics Institute with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in computer science and an important step in the development of the theory of computational complexity. Levin's journal article on this theorem was published in 1973;[5] he had lectured on the ideas in it for some years before that time (see Trakhtenbrot's survey),[6] though complete formal writing of the results took place after Cook's publication.
Levin was awarded the Knuth Prize in 2012[7] for his discovery of NP-completeness and the development of average-case complexity.
He is currently a professor of computer science at Boston University, where he began teaching in 1980.
Notes
- ↑ 1.0 1.1 Levin's curriculum vitae
- ↑ 1971 Dissertation (in Russian); English translation at arXiv
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found. (pdf)
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ ACM press release, August 22, 2012
References
- Lua error in package.lua at line 80: module 'strict' not found.
External links
- Levin's home page at Boston University.
- 2012 Knuth Prize to Leonid Levin
- Pages with broken file links
- Articles containing Russian-language text
- Articles containing Ukrainian-language text
- 1948 births
- American computer scientists
- American Jews
- American people of Russian-Jewish descent
- 20th-century American mathematicians
- 21st-century American mathematicians
- Boston University faculty
- Russian information theorists
- Living people
- Massachusetts Institute of Technology alumni
- Moscow State University alumni
- People from Dnipropetrovsk
- Russian computer scientists
- Russian mathematicians
- Russian Jews
- Soviet computer scientists
- Soviet mathematicians
- Soviet emigrants to the United States
- American information theorists
- Alexander von Humboldt Fellows
