Alexander Alexandrowitsch Rasborow
Alexander Alexandrowitsch Rasborow (, 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 Adjan 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). In Teilzeit ist er auch (2012) noch am Steklow-Institut sowie am Toyota Technological Institute in Chicago.

1990 erhielt er den Nevanlinna-Preis für seine Methode, untere Grenzen für die Schaltkreiskomplexität (Boolean Circuit Complexity) zu finden. Er zeigte, dass die Lücke in der Schaltkreiskomplexität zwischen monotonen Booleschen Funktionen (solche aufgebaut aus logischen und, oder und Identität, nicht mit Negation) und nicht-monotonen Super-polynomial sein kann (von Noga Alon/R. B. Boppana und Éva Tardos auf exponentiell verbessert).

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. 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.

In der extremalen Graphentheorie erzielte er Teilresultate beim Cliquen-Dichte-Problem von László Lovász und Miklós Simonovits (allgemein gelöst 2016 von Christian Reiher).

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.

2013 erhielt er den David P. Robbins Prize der American Mathematical Society für seine Arbeit "On the minimal density of triangles in graphs" und für die Einführung von Flaggen-Algebren (Flag Algebras) als mächtige neue Methode in die extremale Kombinatorik. Rasborow löste damit ein altes lange offenes Problem der extremalen Kombinatorik, die Frage nach der minimalen Anzahl von Dreiecken in Graphen mit n Ecken und m Kanten.

2020 wurde Rasborow in die American Academy of Arts and Sciences gewählt.

}}
Q2320
6. Februar
TIME
Q2755
1963
TIME
Q104717
Belowo
LOC
Q159
russischer
LOC
Q13164
Lomonossow-Universität
ORG
Q2074389
Sergei Adjan
PER
Q611420
Steklow-Institut
LOC
Q131252
University of Chicago
ORG
Q21578
Princeton University
ORG
Q635642
Institute for Advanced Study
LOC
Q902556
Nevanlinna-Preis
MEDIA
None
Schaltkreiskomplexität
UNK
Q92927
Noga Alon
PER
Q15030
Éva Tardos
PER
Q93146
Steven Rudich
PER
Q1417143
Gödel-Preis
EVE
Q746242
P-NP-Problem
Concept
Q8789
kryptographische
Concept
Q1137554
NP-schwer
MISC
Q864003
diskreten Logarithmus
Concept
Q727000
Clay-Probleme
Concept
Q357918
László Lovász
PER
Q1288727
Miklós Simonovits
PER
Q5110071
Christian Reiher
PER
Q83172
Russischen Akademie der Wissenschaften
ORG
Q1291783
Tarski Lectures
EVE
Q337234
Academia Europaea
ORG
Q860611
ICM
LOC
Q484678
Berkeley
LOC
Q1559188
Gödel-Lecturer
MEDIA
Q25392300
David P. Robbins Prize
UNK
Q463303
American Academy of Arts and Sciences
LOC
Q93019
Alexander Alexandrowitsch Rasborow
PER
1963-02-06T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
6. Februar 1963
DATE
1991-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1991
DATE
1999-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1999
DATE
1993-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
und 1993
DATE
2000-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
und 2000
DATE
2003-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2003
DATE
2012-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2012
DATE
1990-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1990
DATE
2007-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2007
DATE
2000-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2000
DATE
1998-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1998
DATE
1986-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1986
DATE
2010-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2010
DATE
2013-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2013
DATE
2020-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2020
DATE
+1991^^http://www.w3.org/2001/XMLSchema#decimal
1991
NUMBER
+1999^^http://www.w3.org/2001/XMLSchema#decimal
1999
NUMBER
+2003^^http://www.w3.org/2001/XMLSchema#decimal
2003
NUMBER
+2012^^http://www.w3.org/2001/XMLSchema#decimal
2012
NUMBER
+1990^^http://www.w3.org/2001/XMLSchema#decimal
1990
NUMBER
+2007^^http://www.w3.org/2001/XMLSchema#decimal
2007
NUMBER
+2000^^http://www.w3.org/2001/XMLSchema#decimal
2000
NUMBER
+1998^^http://www.w3.org/2001/XMLSchema#decimal
1998
NUMBER
+1986^^http://www.w3.org/2001/XMLSchema#decimal
1986
NUMBER
+2010^^http://www.w3.org/2001/XMLSchema#decimal
2010
NUMBER
+2013^^http://www.w3.org/2001/XMLSchema#decimal
2013
NUMBER
+2020^^http://www.w3.org/2001/XMLSchema#decimal
2020
NUMBER
place of birth
country of citizenship
educated at
doctoral advisor
employer
award received
award received
member of
member of
award received
member of
country
award received