Aleksandr Razborov

Aleksandr Aleksandrovič Razborov (Belovo, 16 febbraio 1963) è un matematico russo.

È professore presso l'Università di Chicago.

Ricerca

Nel suo lavoro più noto, insieme a Steven Rudich, ha introdotto la nozione di dimostrazioni naturali, una classe di strategie utilizzate per dimostrare i limiti inferiori fondamentali nella complessità computazionale. In particolare, Razborov e Rudich hanno mostrato che, assumendo che esistano certi tipi di funzioni unidirezionali, tali dimostrazioni non possono dare una risoluzione del problema P = NP, quindi saranno necessarie nuove tecniche per risolvere questo problema.

Premi

Premio Nevanlinna (1990) per aver introdotto il "metodo di approssimazione" nel dimostrare i limiti inferiori del circuito booleano di alcuni problemi algoritmici essenziali,
Docente di Erdős, Università Ebraica di Gerusalemme, 1998.
Membro corrispondente dell'Accademia delle scienze russa (2000)
Premio David P. Robbins per l'articolo "Sulla densità minima dei triangoli nei grafici" (Combinatorics, Probability and Computing 17 (2008), n. 4, 603–618), e per aver introdotto un nuovo potente metodo, flag algebras, per risolvere problemi di combinatoria estrema
Premio Gödel (2007, con Steven Rudich) per il documento "Natural Proofs".
Illustre professore di servizio (2008) presso il Dipartimento di Informatica, Università di Chicago.
Membro dell'American Academy of Arts and Sciences (AAAS) (2020).