Jump to content

Leonid Levin

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Miym (talk | contribs) at 00:57, 23 January 2010 (name in Hebrew looks unsourced, removing for now). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Leonid Anatolievich Levin
Born (1948-11-02) November 2, 1948 (age 75)
Alma materMoscow University
Known forresearch in complexity, randomness, information
Scientific career
FieldsComputer Science
InstitutionsBoston University
Doctoral advisorAndrey Kolmogorov, Albert R. Meyer

Leonid Anatolievich Levin (Russian: Леонид Анатольевич Левин; Phonetic: Le-oh-NEED Le-vin; born November 2, 1948 in Dnipropetrovsk Ukrainian SSR) is a Russian-American computer scientist.

He obtained his master degree in 1970 and a Ph.D. equivalent in 1972 at Moscow University where he studied under Andrey Kolmogorov. Later, he emigrated to the U.S. in 1978 and also earned a Ph.D. at the Massachusetts Institute of Technology (MIT) in 1979. 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[1], 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.[2]

Levin independently discovered a theorem also proven by Stephen Cook. This NP-completeness theorem, often called the 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)[3], 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.

See also

Notes

  1. ^ Leonid Levin. Average-case complete problems. SIAM J. Comput., 15:285–286, 1986
  2. ^ Shasha, Dennis (1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Springer. ISBN 0-387-97992-1. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help); Unknown parameter |month= ignored (help)
  3. ^ Boris A. Trakhtenbrot (1984). "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms". Annals of the History of Computing. 6 (4). IEEE: 384–400. doi:10.1109/MAHC.1984.10036.

References


Template:Persondata