Jewish Biography

Related Links

Jewish Memoirs
List of Jews
List of Rabbis
Actors & Actresses
American authors
Jewish Chefs
Chess Players
Computer Scientists
Film Directors
Jewish Americans
Jewish Comedians
Jewish CEOs
Jewish Comics
Jewish Dancers
Jewish Head States
Jewish Magicians
Jewish Models
Jewish Producers
Jewish Poker Players
Jewish Philosopher
Jewish Theater
Jewish TV
Jewish Radio
Motion Pictures
Music businessmen
Jewish Poets
Jewish Cartoonist
Jewish Women
Featured Jews
Harry Houdini
Hogan's Heroes
Marx Brothers
The Three Stooges

-- Jewish Links --

Jewish Books
Jewish Links
Jewish Catalogs
Jewish Posters
Jewish Stories
Jewish Videos
Kosher Wines
Jewish Biography --> Biographies --> List of Jews --> Famous Jewish American Computer Scientists
Sponsored listings for Jewish Recipes and Kosher Cooking

Leonid Anatolievich Levin (Hebrew: לאוניד אנטולייביץ לוין‎; Russian: Леонид Анатольевич Левин; born November 2, 1948 in Dnipropetrovsk Ukrainian SSR) is a computer scientist. He studied under Andrey Kolmogorov.

He obtained his master degree in 1970 and first Ph.D. in 1972 at Moscow University. Later, he emigrated to the U.S. 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 of the book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.[1]

Levin independently discovered a theorem that was also discovered and proven by Stephen Cook. This NP-completeness theorem, often called by inventors' names (see Cook-Levin Theorem) was a basis for one of the seven "Millennium Math. Problems" declared by Clay Mathematics Institute with a $1,000,000 prize offered. It 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 had lectured on the ideas in it for some years before that time (see Trakhtenbrot's survey)[2], though complete formal writing of the results took place after Cook's publication.

He is currently a professor of computer science at Boston University, where he began teaching in 1980.

Aharon's Jewish Books and Judaica
600 South Holly Street Suite 103
Denver, Colorado 80246

Map to Aharon's Jewish Books and Judaica

Store Hours

Monday through Thursday 9 AM to 6 PM
Friday 9 AM to 2 PM
Sunday 9 AM to 4 PM


Jewish Biography | About Jewish Biography | Search

This article is licensed under the GNU Free Documentation License. It uses material from the