Leonid Levin (born November 2, 1948, in Dnipropetrovsk, Ukrainian SSR, Soviet Union) is a Soviet-American mathematician and computer scientist who has taught computer science at Boston University since 1980. His research addresses randomness in computing, algorithmic complexity, average-case complexity and information theory. Levin and Stephen Cook independently discovered the existence of NP-complete problems, a result known as the Cook-Levin theorem that became foundational to computational complexity theory. He received the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity, and is a member of the United States National Academy of Sciences and a Fellow of the American Academy of Arts and Sciences.
Facts
Connections
In Field
Source Leonid Levin (Wikipedia)
In the Other Atlases
Nationality
Also in Geography Atlas: the nationality of this subject.
Also in Geography Atlas: the nationality of this subject.
Sources
1. Wikidata: Leonid Levin
- Wikidata Q92966, resolved via en.wikipedia pageprops (wave rule R-L)
- Wikidata Q92966 P569 (date of birth)
View the SourceLeonid Levin (Wikipedia)
In Field: Theory of Computation, LeadQuote, In Field: Theory of Computation, Lead
He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.