Leonid A. Levin was born on November 2, 1948 in Dnepropetrovsk, Ukraine.
He wrote his doctoral thesis in 1971 under Kolmogorov,
but was denied his Ph. D. for political reasons.
In 1973, he published a paper in which he independently
discovered results of Stephen Cook and
Richard Karp on NP-completeness.
Levin emigrated to the US in 1978 and now teaches at Boston University.
He is well-known for his habit of publishing extremely short papers, some
only one page long.
- Dennis Shasha and Cathy Lazere, Out of Their Minds: The Lives and
Discoveries of 15 Great Computer Scientists, Copernicus, 1995.
Back to Theory of Computing Hall of Fame Main Page
Back to CS 462 home page