Leonid Levin
Leonid Anatolievich Levin | |
---|---|
Born | |
Alma mater | Moscow University Massachusetts Institute of Technology |
Known for | research in complexity, randomness, information |
Awards | Knuth Prize (2012) |
Scientific career | |
Fields | Computer Science |
Institutions | Boston University |
Doctoral advisor | Andrey Kolmogorov, Albert R. Meyer |
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
- ^ a b 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[dead link]. 6 (4). IEEE: 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
- 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