Background
Levin, Leonid A. was born on November 2, 1948 in Dnepropetrousk, Ukraine. Son of Anatoly A. and Anna Levin.
mathematician computer scientist
Levin, Leonid A. was born on November 2, 1948 in Dnepropetrousk, Ukraine. Son of Anatoly A. and Anna Levin.
He obtained his master"s degree at Moscow University in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972. After researching in algorithmic problems of information theory at the Moscow Institute of Information Transmission of the National Academy of Sciences 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 United States. in 1978 and also earned a Doctor of Philosophy at the Massachusetts Institute of Technology (Massachusetts Institute of Technology) in 1979.
His advisor at Massachusetts Institute of Technology 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 Natural Philosophy-complete problems.
The Cook–Levin theorem was a breakthrough in computer science and an important step in the development of the theory 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.
Married Larissa V. Lastovetskaya, September 3, 1977. Children: Rebecca A., Naomi T., Andrei J.
