Leonid Levin

From Wikipedia, the free encyclopedia
Leonid Anatolievich Levin
Born (1948-11-02) 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

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 degree at Moscow University in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972 but was never granted the degree formally for political reasons. Later, 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,[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.[2]

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

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

See also

Notes

  1. ↑ Levin, Leonid (1986). "Average-case complete problems". SIAM J. Comput. 15 (1): 285–6. doi:10.1137/0215020. 
  2. ↑ 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. 
  3. ↑ Levin, Leonid (1973). "Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (Russian: Проблемы передачи информации, Problemy Peredachi Informatsii) 9 (3): 115–116.  (pdf)
  4. ↑ 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. 
  5. ↑ ACM press release, August 22, 2012

References

External links

Knuth Prize laureates
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.