Alexander Razborov

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

Aleksandr Aleksandrovich Razborov (Russian: Алекса́ндр Алекса́ндрович Разбо́ров,English: Alexander Razborov; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist.


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]