Leonid Anatolievich Levin ( ; russian: Леони́д Анато́льевич Ле́вин; uk, Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (a ...

. He is known for his work in

randomness In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...

computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, ...

algorithmic complexity Algorithmic may refer to: *Algorithm, step-by-step instructions for a calculation **Algorithmic art, art made by an algorithm **Algorithmic composition, music made by an algorithm **Algorithmic trading, trading decisions made by an algorithm ** Alg ...

and intractability,

average-case complexity In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case com ...

, foundations of

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

algorithmic probability In algorithmic information theory, algorithmic probability, also known as Solomonoff probability, is a mathematical method of assigning a prior probability to a given observation. It was invented by Ray Solomonoff in the 1960s. It is used in induc ...

theory of computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how algorithmic efficiency, efficiently they can be solved or t ...

, and

information theory Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. ...

. He obtained his master's degree at

Moscow University M. V. Lomonosov Moscow State University (MSU; russian: Московский государственный университет имени М. В. Ломоносова) is a public research university in Moscow, Russia and the most prestigious ...

in 1970 where he studied under

Andrey Kolmogorov Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...

and completed the Candidate Degree academic requirements in 1972. He and Stephen Cook independently discovered the existence of

NP-complete problems In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

. 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 The Clay Mathematics Institute (CMI) is a private, non-profit foundation dedicated to increasing and disseminating mathematical knowledge. Formerly based in Peterborough, New Hampshire, the corporate address is now in Denver, Colorado. CMI's sc ...

with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in

and an important step in the development of the theory of

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

. Levin was awarded the Knuth Prize in 2012 for his discovery of NP-completeness and the development of

. He is a member of the US

National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nat ...

and a fellow of the

American Academy of Arts and Sciences The American Academy of Arts and Sciences (abbreviation: AAA&S) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, a ...

Biography

He obtained his master's degree at

in 1970 where he studied under

and completed the Candidate Degree academic requirements in 1972.Levin's curriculum vitae
/ref> After researching algorithmic problems of information theory at the Moscow Institute of Information Transmission of the

in 1972–1973, and a position as Senior Research Scientist at the Moscow National Research Institute of Integrated Automation for the Oil/Gas Industry in 1973–1977, he emigrated to the U.S. in 1978 and also earned a Ph.D. at the

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of th ...

(MIT) in 1979. His advisor at MIT was Albert R. Meyer. He is well known for his work in

and intractability,

, foundations of

and

, 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 independently discovered the existence of

. This NP-completeness theorem, often called the Cook–Levin theorem, was a basis for one of the seven Millennium Prize Problems declared by the

with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in

and an important step in the development of the theory of

. Levin's journal article on this theorem was published in 1973;(pdf)
/ref> 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. Levin was awarded the Knuth Prize in 2012ACM press release, August 22, 2012
for his discovery of NP-completeness and the development of

. He is currently a professor of computer science at

Boston University Boston University (BU) is a private research university in Boston, Massachusetts. The university is nonsectarian, but has a historical affiliation with the United Methodist Church. It was founded in 1839 by Methodists with its original cam ...

, where he began teaching in 1980.

Notes

References

External links

Levin's home page
at Boston University.

{{DEFAULTSORT:Levin, Leonid 1948 births Living people Scientists from Dnipro Massachusetts Institute of Technology alumni Moscow State University alumni American computer scientists American people of Ukrainian-Jewish descent 20th-century American mathematicians 21st-century American mathematicians Boston University faculty Russian information theorists Russian computer scientists Russian mathematicians Soviet computer scientists Soviet mathematicians Soviet emigrants to the United States American information theorists 21st-century Russian politicians Knuth Prize laureates Ukrainian mathematicians Ukrainian Jews