Leonid Levin

from Wikipedia, the free encyclopedia
Leonid Levin (2010)

Leonid Levin ( Russian Леони́д Анато́льевич Ле́вин , Leonid Anatoljewitsch Levin ; born November 2, 1948 in Dnepropetrovsk , Ukrainian SSR ) is a Soviet-American computer scientist .

biography

Levin is of Jewish descent and was born in 1948 in Soviet Dnepropetrovsk . His father was a teacher of Russian language and literature, his mother an industrial architect. Levin won first place at the Kiev City Physics Olympiad and entered a special school at Kiev University for gifted students. Here he also heard a lecture by Andrei Kolmogorow in 1963 , who also posed some problems for him and invited him to his own school for talented students in Moscow. He studied at Lomonosov University , where he obtained his mathematics diploma in 1970, studied with Kolmogorov and in 1972 acquired the requirements for a doctorate ( candidate title ), which he was then refused for political reasons. Levin had made himself unpopular in communist circles through his statements (at the same time, after the events in the CSSR, a wave of purges began, which was aimed primarily at Jewish students and barred them from access to higher education or made it extremely difficult). He wrote his dissertation on Kolmogorov complexity . In 1973 he developed a theory of NP-completeness , independently of the efforts at that time in the West ( Stephen Cook ) , which was ignored in the West for about ten years. The set of Cook is now referred to as a set of Cook and Levin. Levin then worked in various Soviet institutes such as the Institute for Information Transmission and the Institute for Automation of the Oil and Gas Industry. However, he was denied access to the university. In 1978 he emigrated to the USA . Here he did his second doctorate in 1979 at the Massachusetts Institute of Technology ( A concept of independence with applications in various fields of mathematics ). From 1980 he was associate professor and from 1984 professor at Boston University .

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

Levin's important research fields were the study of chance in computer science , complexity theory , mathematical foundations of computer science, probabilistic algorithms and information theory .

For 2012 he was awarded the Knuth Prize . In 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 ). In 2014 he was elected to the American Academy of Arts and Sciences and in 2019 to the National Academy of Sciences .

literature

  • Dennis Shasha, Cathy Lazere: Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists , ISBN 0-387-97992-1 .

Web links

Commons : Leonid Levin  - collection of pictures, videos and audio files

Individual evidence

  1. ↑ Dennis Sasha, Cathy Lavere Out of their minds , p. 152 quotes him as follows: Loud and arrogant, I was the ideal scapegoat that the communists at the university needed at this time , Noisy and arrogant, I was an excellent scapegoat which the university communist authorities needed at that time .
personal data
SURNAME Levin, Leonid
ALTERNATIVE NAMES Левин, Леонид Анатольевич (Russian)
BRIEF DESCRIPTION Soviet-American computer scientist
DATE OF BIRTH November 2, 1948
PLACE OF BIRTH Dnepropetrovsk , Soviet Union