Leonid Levin
Encyclopedia
Leonid Anatolievich Levin (Le-oh-NEED LE-vin; ; born November 2, 1948 in Dnipropetrovsk
, Ukraine
) is a Soviet-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
, 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.
Levin and Stephen Cook
independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook-Levin Theorem, was a basis for one of the seven Millennium Prize Problems
declared by the Clay Mathematics Institute
with a $1,000,000 prize offered. The Cook–Levin theorem 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), 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.
Dnipropetrovsk
Dnipropetrovsk or Dnepropetrovsk formerly Yekaterinoslav is Ukraine's third largest city with one million inhabitants. It is located southeast of Ukraine's capital Kiev on the Dnieper River, in the south-central region of the country...
, Ukraine
Ukrainian SSR
The Ukrainian Soviet Socialist Republic or in short, the Ukrainian SSR was a sovereign Soviet Socialist state and one of the fifteen constituent republics of the Soviet Union lasting from its inception in 1922 to the breakup in 1991...
) is a Soviet-American computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
.
He obtained his master degree in 1970 and a Ph.D.
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
equivalent in 1972 at Moscow University where he studied under Andrey Kolmogorov
Andrey Kolmogorov
Andrey Nikolaevich Kolmogorov was a Soviet mathematician, preeminent in the 20th century, who advanced various scientific fields, among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity.-Early life:Kolmogorov was born at Tambov...
. Later, he emigrated to the U.S.
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
in 1978 and also earned a Ph.D. at the Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
(MIT) in 1979. His advisor at MIT was Albert R. Meyer
Albert R. Meyer
Albert Ronald da Silva Meyer is a professor of computer science at Massachusetts Institute of Technology . He has been a Fellow of the American Academy of Arts and Sciences since 1987, and he was inducted as a Fellow of the Association for Computing Machinery in 2000.Meyer's seminal works...
.
He is well known for his work in randomness
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
in computing
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, algorithmic complexity and intractability, average-case complexity
Average-case complexity
Average-case complexity is a subfield of computational complexity theory that studies the complexity of algorithms on random inputs.The study of average-case complexity has applications in the theory of cryptography....
, foundations of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, algorithmic probability
Algorithmic probability
In algorithmic information theory, algorithmic probability is a method of assigning a probability to each hypothesis that explains a given observation, with the simplest hypothesis having the highest probability and the increasingly complex hypotheses receiving increasingly small probabilities...
, theory of computation
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
, and information theory
Information theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
.
His life is described in a chapter of the book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.
Levin and Stephen Cook
Stephen Cook
Stephen Arthur Cook is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity...
independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook-Levin Theorem, was a basis for one of the seven Millennium Prize Problems
Millennium Prize Problems
The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000. As of September 2011, six of the problems remain unsolved. A correct solution to any of the problems results in a US$1,000,000 prize being awarded by the institute...
declared by the Clay Mathematics Institute
Clay Mathematics Institute
The Clay Mathematics Institute is a private, non-profit foundation, based in Cambridge, Massachusetts. The Institute is dedicated to increasing and disseminating mathematical knowledge. It gives out various awards and sponsorships to promising mathematicians. The institute was founded in 1998...
with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and is the foundation of computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*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
Boris Trakhtenbrot
Boris Avraamovich Trakhtenbrot or Boaz Trakhtenbrot is an Israeli and Russian mathematician in mathematical logic, algorithms, theory of computation and cybernetics. He worked at Akademgorodok, Novosibirsk during the 1960s and 1970s...
's survey), though complete formal writing of the results took place after Cook's publication.
He is currently a professor of computer science at Boston University
Boston University
Boston University is a private research university located in Boston, Massachusetts. With more than 4,000 faculty members and more than 31,000 students, Boston University is one of the largest private universities in the United States and one of Boston's largest employers...
, where he began teaching in 1980.
External links
- Levin's home page at Boston University.