Leonid Levin

Leonid Levin (Russian Леонид Анатольевич Левин ); Anatoljevich Leonid Levin, ( born November 2, 1948 in Dnipropetrovsk, Ukrainian SSR ) is an American computer scientist.

Biography

Levin is Jewish and was born in 1948 in the then Soviet Dnepropetrovsk. His father was a teacher of Russian language and literature, and his mother an architect in the industry. Levin won at the Physics Olympiad the city of Kiev the first place, and came in a special school for gifted students at the University of Kiev. Here he heard a lecture by Andrei Kolmogorov in 1963, who also asked him some problems and invited him to his own gifted school in Moscow. He studied at the Moscow State University, where he in 1970 his diploma in mathematics, studied with Kolmogorov 1972 and the requirements for a doctoral degree earned ( candidate items), but which was then refused on political grounds him. Levin had made himself unpopular by his remarks in Communist circles (at the same time continued after the events in Czechoslovakia a purge that was directed primarily against Jewish students and they blocked the access to higher education or enormously difficult ). His dissertation he wrote about Kolmogorov complexity. In 1973, he developed independently of the former efforts in the West ( Stephen Cook) a theory of NP- completeness, which remained unnoticed for about ten years in the West. The set of Cook is now also referred to as a set of Cook and Levin. Levin then worked in various Soviet institutions such as the Institute for Information Transmission and the Institute of Automation of the oil and gas industry. The road to the University, however, was denied. In 1978 he emigrated to the United States. Here he received his doctorate for a second time in 1979 at the Massachusetts Institute of Technology (A concept of independence with applications in various fields of mathematics ). From 1980 he was an associate professor and from 1984 professor at Boston University.

He was a visiting professor in 1986 at the University of California, Berkeley, 1987 at Caltech, 1993/94 at the Hebrew University, and from 1999 at the University of London, 2001/ 02 at the IHES and Clay Mathematics Institute and 2010 at the University of Heidelberg.

Important research fields Levin were the investigation of randomness in computer science, complexity theory, mathematical foundations of computer science, probabilistic algorithms and information theory.

In 2012 he was awarded the Knuth Prize. 1993/94 he was a Guggenheim Fellow. In 1994 he was invited speaker at the International Congress of Mathematicians in Zurich ( Randomness and non determinism ).