Alexander Razborov
| Alexander Razborov | |
|---|---|
| Born |
February 16, 1963 Belovo, Russian SFSR, Soviet Union |
| Nationality | United States, Russia |
| Fields | Mathematician |
| Institutions | University of Chicago, Steklov Mathematical Institute, 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) David P. Robbins Prize (2013) |
Aleksandr Aleksandrovich Razborov (Russian: Алекса́ндр Алекса́ндрович Разбо́ров; 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.
...
Wikipedia