Leonid Levin
Mirror of English Wikipedia, the free encyclopedia
Categories: Mathematician stubs | 1948 births | Living people | Computer scientists | American mathematicians | Russian mathematicians | Jewish mathematicians | Erdős number 2
Leonid Levin (born November 2, 1948, USSR) is a computer scientist. He studied under Andrey Kolmogorov.
He obtained his first Ph.D. in 1972 at Moscow University. Later, he emigrated to the USA in 1978 and earned another Ph.D at the Massachusetts Institute of Technology in 1979.
He is well known for his work in randomness in computing, algorithmic complexity and intractability, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory.
His life is described in a chapter in the book: Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.
Levin independently discovered a theorem that was also discovered and proven by Stephen Cook. The theorem, which is known as the Cook or Cook-Levin theorem, was a breakthrough in computer science and is the foundation of computational complexity. Levin's journal article on this theorem was published in 1973; he reports that he had lectured on it for some years before that time (see Trakhtenbrot's survey below).
He is currently a professor of computer science at Boston University, where he began teaching in 1980.
External links
- Leonid Levin's home page
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms, by B.A. Trakhtenbrot, in the Annals of the History of Computing, 6(4):384-400, 1984.
