Alexander Alexandrowitsch Rasborow

Alexander Alexandrowitsch Rasborow (russisch Александр Александрович Разборов, englische Transliteration Alexander Razborov; * 6. Februar 1963 in Belowo) ist ein russischer Informatiker und Mathematiker.

Rasborow studierte 1980 bis 1985 an der Lomonossow-Universität (Fakultät für Mathematik und Mechanik) und nach dem Diplom von 1985 bis 1987 bei Sergei Adian am Steklow-Institut, bei dem er 1987 promovierte (Über Systeme von Gleichungen in freien Gruppen). Danach war er Forscher am Steklow Institut, ab 1991 als Leiter einer Arbeitsgruppe (Leading Researcher) und ab 2008 mit dem Titel Principal Researcher. 1991 erhielt er den russischen Doktorgrad (Untere Grenzen in der Booleschen Komplexität). Seit 2008 ist er Andrew McLeish Distinguished Service Professor in der Fakultät für Informatik der University of Chicago. 1999 bis 2000 war er Gastwissenschaftler an der Princeton University und 1993 bis 1994 und 2000 bis 2008 war er am Institute for Advanced Study (2003 bis 2008 als Gastprofessor).

1990 erhielt er den Nevanlinna-Preis für seine Methode, untere Grenzen für die Schaltkreiskomplexität (Boolean Circuit Complexity) zu finden.^[1]

2007 erhielt er mit Steven Rudich den Gödel-Preis für ihre Arbeit Natural Proof, die zeigte, dass Schaltkreiskomplexitätsmethoden zur Bestimmung einer Untergrenze der Komplexität eines Problems wahrscheinlich nicht geeignet sind, das P=NP-Problem zu lösen.^[2]. Dabei isolierten sie eine gemeinsame Eigenschaft dieser Schaltkreiskomplexitäts-Verfahren, die sie Natural Proof nennen. Sie zeigten, dass ein Natural Proof-Beweis für das P=NP Problem zur Folge hätte, dass keine Pseudozufallsgeneratoren existieren, was aber allgemein angenommen wird. Weiter zeigten sie, dass es keine Natural Proof Beweise dafür gibt, dass einige bekannte kryptographische Probleme NP-schwer sind (wie die Faktorisierung ganzer Zahlen oder das Problem des diskreten Logarithmus). Die Arbeit von Razborov und Rudich war ein wichtiger Fortschritt im P=NP Problem, einem der Clay-Probleme, der zeigte, dass man in neuen Richtungen nach der Lösung suchen musste.

Seit 2000 ist er korrespondierendes Mitglied der Russischen Akademie der Wissenschaften. 2000 hielt er die Tarski Lectures. Seit 1993 ist er Mitglied der Academia Europaea. 1998 hielt er die Paul Erdös Lectures in Jerusalem und die Coxeter Lectures beim Fields Institute in Toronto. 1986 war er Invited Speaker auf dem ICM in Berkeley (Lower bounds for monotone complexity of boolean functions). 2010 war er Gödel-Lecturer.

Schriften

• The P=NP problem, a view from the 1990s, in Bolibruch, Osipov, Sinai (Herausgeber) Mathematical Events of the Twentieth Century, Springer 2006, S. 331

Weblinks

• Homepage in Chicago
• Gödel Preis für Razborov

Einzelnachweise

1. ↑ Razborov Lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Doklady, Bd.31, 1985, S.354
2. ↑ Razborov, Rudich Natural Proof, Journal of Computer and System Sciences, Bd. 55, 1997, S. 24-35 und Proc. 26. Int. ACM Symposium on the Theory of Computing (STOC), 1994, S.204, Online hier, Postcript Datei