Leonid Levin

Leonid Levin (2010)

Leonid Levin (russisch Леони́д Анато́льевич Ле́вин); Leonid Anatoljewitsch Lewin, (* 2. November 1948 in Dnepropetrowsk, Ukrainische SSR) ist ein amerikanischer Informatiker.

Biografie

Levin ist jüdischer Herkunft und wurde 1948 im damals noch sowjetischen Dnepropetrowsk geboren. Sein Vater war Lehrer für Russische Sprache und Literatur, seine Mutter Architektin in der Industrie. Levin gewann bei der Physik-Olympiade der Stadt Kiew den Ersten Platz und kam in eine Spezialschule der Universität Kiew für begabte Schüler. Hier hörte er auch 1963 einen Vortrag von Andrei Kolmogorow, der ihm auch einige Probleme stellte und ihn auf seine eigene Begabtenschule in Moskau einlud. Er studierte an der Lomonossow-Universität, an der er 1970 sein Mathematikdiplom erwarb, bei Kolmogorov studierte und 1972 die Voraussetzungen für eine Promotion erwarb (Kandidatentitel), die ihm dann aber aus politischen Gründen verweigert wurde. Levin hatte sich durch seine Äußerungen in kommunistischen Kreisen unbeliebt gemacht (gleichzeitig setzte damals nach den Ereignissen in der CSSR eine Säuberungswelle ein, die sich vor allem gegen jüdische Studenten richtete und ihnen den Zugang zu höherer Ausbildung versperrte oder enorm erschwerte). Seine Dissertationsarbeit schrieb er über Kolmogorov-Komplexität. 1973 entwickelte er unabhängig von den damaligen Bestrebungen im Westen (Stephen Cook) eine Theorie der NP-Vollständigkeit, die im Westen für ca. zehn Jahre unbeachtet blieb. Der Satz von Cook wird heute auch als Satz von Cook und Levin bezeichnet. Levin arbeitete danach in verschiedenen sowjetischen Instituten wie dem Institut für Informationsübertragung und dem Institut für Automatisierung der Öl- und Gasindustrie. Der Weg an die Universität war ihm jedoch verwehrt. 1978 emigrierte er in die USA. Hier promovierte er ein zweites Mal 1979 am Massachusetts Institute of Technology (A concept of independence with applications in various fields of mathematics). Ab 1980 war er Associate Professor und ab 1984 Professor an der Boston University.

Er war Gastprofessor 1986 an der University of California, Berkeley, 1987 am Caltech, 1993/94 an der Hebrew University, ab 1999 an der Universität London, 2001/02 am IHES und Clay Mathematics Institute und 2010 an der Universität Heidelberg.

Wichtige Forschungsfelder Levins waren die Untersuchung des Zufalls in der Informatik, die Komplexitätstheorie, mathematische Grundlagen der Informatik, probabilistische Algorithmen und Informationstheorie.

Für 2012 erhielt er den Knuth-Preis zugesprochen. 1993/94 war er Guggenheim Fellow. 1994 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Zürich (Randomness and non determinism).

Literatur

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

Weblinks

• Website von Leonid Levin mit CV (englisch)