Quantcast
peoplepill id: leonid-levin
LL
1 views today
1 views this week
Leonid Levin

Leonid Levin Russian mathematician

Russian mathematician
The basics
Quick Facts
Intro Russian mathematician
Known for Cook–Levin theorem
A.K.A. Leonid Lewin
Is Mathematician Computer scientist
From United States of America Russia
Type Mathematics Science Technology
Gender male
Birth 2 November 1948, Dnipro, Ukraine
Age: 71 years
Star sign ScorpioScorpio
The details
Biography

Leonid Anatolievich Levin (/l.ˈnd ˈ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, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory. 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.

He 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 was awarded the Knuth Prize in 2012 for his discovery of 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.

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. 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. 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, 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.

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; he had lectured on the ideas in it for some years before that time (see Trakhtenbrot's survey), though complete formal writing of the results took place after Cook's publication.

Levin was awarded the Knuth Prize in 2012 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.

The contents of this page are sourced from Wikipedia article. The contents are available under the CC BY-SA 4.0 license.
comments so far.
Comments
Reference sources
References
http://epubs.siam.org/doi/abs/10.1137/0215020
//doi.org/10.1137%2F0215020
http://www.cs.bu.edu/fac/lnd/research/curv.htm
http://www.acm.org/press-room/news-releases/2012/sigact-knuth-prize-2012
https://web.archive.org/web/20160303200335/http://www.acm.org/press-room/news-releases/2012/sigact-knuth-prize-2012
https://archive.org/details/isbn_9780387979922
http://www.cs.bu.edu/fac/lnd/dvi/diss/1-dis.pdf
https://arxiv.org/abs/1009.5894
http://www.mathnet.ru/php/getFT.phtml?jrnid=ppi&paperid=914&volume=9&year=1973&issue=3&fpage=115&what=fullt&option_lang=eng
https://www.computer.org/csdl/mags/an/1984/04/man1984040384-abs.html
//doi.org/10.1109%2FMAHC.1984.10036
arrow-left arrow-right arrow-up arrow-down instagram whatsapp myspace quora soundcloud spotify tumblr vk website youtube stumbleupon comments comments pandora gplay iheart tunein pandora gplay iheart tunein itunes