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

Research

In his most famous work, completed with Steven Rudich, he introduced the idea of natural proofs, which are methods used to establish important limits on problem-solving efficiency in computational complexity. Specifically, Razborov and Rudich demonstrated that if certain special types of one-way functions exist, these proofs cannot provide a solution to the question of whether P equals NP. Therefore, new methods will be needed to address this problem.

Awards

• Nevanlinna Prize (1990) for developing the "approximation method" to prove limits on how efficiently certain important algorithmic problems can be solved by computer circuits.
• Erdős Lecturer, Hebrew University of Jerusalem, 1998.
• Corresponding member of the Russian Academy of Sciences (2000).
• Gödel Prize (2007, with Steven Rudich) for the paper "Natural Proofs."
• David P. Robbins Prize for the paper "On the minimal density of triangles in graphs" (Combinatorics, Probability and Computing 17 (2008), no. 4, 603–618), and for creating a new and effective method called flag algebras to solve problems in extremal combinatorics.
• Gödel Lecturer (2010) with the lecture titled "Complexity of Propositional Proofs."
• Andrew MacLeish Distinguished Service Professor (2008) in the Department of Computer Science, University of Chicago.
• Fellow of the American Academy of Arts and Sciences (AAAS) (2020).