Leonid Levin
| Leonid Anatolievich Levin | |
|---|---|
 | |
| 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.
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 2 Levin's curriculum vitae
- ↑ 1971 Dissertation (in Russian); English translation at arXiv
- ↑ Levin, Leonid (1986). "Average-case complete problems". SIAM J. Comput. 15 (1): 285–6. doi:10.1137/0215020.
- ↑ Shasha, Dennis; Cathy Lazere (September 1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Springer. ISBN 0-387-97992-1.
- ↑ Levin, Leonid (1973). "Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (Russian: Проблемы передачи информации, Problemy Peredachi Informatsii). 9 (3): 115–116. (pdf)
- ↑ Boris A. Trakhtenbrot (1984). "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms". Annals of the History of Computing. IEEE. 6 (4): 384–400. doi:10.1109/MAHC.1984.10036.
- ↑ ACM press release, August 22, 2012
References
- "Leonid A. Levin". Mathematics Genealogy Project.
External links
- Levin's home page at Boston University.
- 2012 Knuth Prize to Leonid Levin