Alexander Razborov

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Alexander Razborov
Born (1963-02-16) February 16, 1963 (age 54)
Belovo, Russian SFSR, Soviet Union
Nationality United States, Russia
Alma mater Moscow State University
Known for group theory, logic in computer science, theoretical computer science
Awards Nevanlinna Prize (1990)
Gödel Prize (2007)
David P. Robbins Prize (2013)
Scientific career
Fields Mathematician
Institutions University of Chicago, Steklov Mathematical Institute, Toyota Technological Institute at Chicago
Doctoral advisor Sergei Adian

Aleksandr Aleksandrovich Razborov (Russian: Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist. He is Andrew McLeish Distinguished Service Professor at the University of Chicago.


In his best known work, joint with Steven Rudich, he introduced the notion of natural proofs, a class of strategies used to prove fundamental lower bounds in computational complexity. In particular, Razborov and Rudich showed that, under the assumption that certain kinds of one-way functions exist, such proofs cannot give a resolution of the P = NP problem, so new techniques will be required in order to solve this question.



See also[edit]


External links[edit]