# Leonid Levin

Leonid Anatolievich Levin | |
---|---|

Born |
Dnipropetrovsk, Ukrainian SSR, Soviet Union | November 2, 1948

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 |

Notable awards | Knuth Prize (2012) |

**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

- 1 2 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*. IEEE.**6**(4): 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