HOME
The Info List - Leonid Levin


--- Advertisement ---



Leonid Anatolievich Levin (/leɪ.oʊˈniːd ˈlɛvɪn/ lay-oh-NEED LEV-in; Russian: Леони́д Анато́льевич Ле́вин; Ukrainian: Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American computer scientist. He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity,[1] foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory. He obtained his master's degree at Moscow University
Moscow University
in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972.[2] He and Stephen Cook
Stephen Cook
independently discovered the existence of NP-complete problems. This NP-completeness
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
Mathematics
Institute with a $1,000,000 prize offered. The Cook–Levin theorem
Cook–Levin theorem
was a breakthrough in computer science and an important step in the development of the theory of computational complexity. Levin was awarded the Knuth Prize
Knuth Prize
in 2012[3] for his discovery of NP-completeness
NP-completeness
and the development of average-case complexity. His life is described in a chapter of the book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.[4]

Contents

1 Biography 2 Notes 3 References 4 External links

Biography[edit] He obtained his master's degree at Moscow University
Moscow University
in 1970 where he studied under Andrey Kolmogorov
Andrey Kolmogorov
and completed the Candidate Degree academic requirements in 1972.[2][5] 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
Massachusetts Institute of Technology
(MIT) in 1979.[2] 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,[1] 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
Stephen Cook
independently discovered the existence of NP-complete problems. This NP-completeness
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
Mathematics
Institute with a $1,000,000 prize offered. The Cook–Levin theorem
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;[6] he had lectured on the ideas in it for some years before that time (see Trakhtenbrot's survey),[7] though complete formal writing of the results took place after Cook's publication. Levin was awarded the Knuth Prize
Knuth Prize
in 2012[3] for his discovery of NP-completeness
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[edit]

^ a b Levin, Leonid (1986). "Average-case complete problems". SIAM J. Comput. 15 (1): 285–6. doi:10.1137/0215020.  ^ a b c Levin's curriculum vitae ^ a b ACM press release, August 22, 2012 Archived March 3, 2016, at the Wayback Machine. ^ a b 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.  ^ 1971 Dissertation (in Russian); English translation at arXiv ^ 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. 

References[edit]

"Leonid A. Levin". Mathematics
Mathematics
Genealogy Project. 

External links[edit]

Wikimedia Commons has media related to Leonid Levin.

Levin's home page at Boston University. 2012 Knuth Prize
Knuth Prize
to Leonid Levin

v t e

Knuth Prize
Knuth Prize
laureates

1990s

Yao (1996) Valiant (1997) Lovász (1999)

2000s

Ullman (2000) Papadimitriou (2002) Ajtai (2003) Yannakakis (2005) Lynch (2007) Strassen (2008)

2010s

Johnson (2010) Kannan (2011) Levin (2012) Miller (2013) Lipton (2014) Babai (2015) Nisan (2016) Goldreich (2017)

Authority control

WorldCat Identities VIAF: 70440154 LCCN: n87126894 MGP: 69211 DB

.