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