Leonid Levin

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.

Sources

  1. 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 360 home page