Professor

Alexander Razborov

University of Chicago
Area
Mathematical and Physical Sciences
Specialty
Mathematics, Applied Mathematics, and Statistics
Elected
2020
Computational complexity theory studies, via rigorous mathematical landmarks such as the P vs. NP problem, the limits of efficient computation. Proving lower bounds is the core intellectual challenge. Razborov made multiple seminal contributions to this area, including lower bounds in circuit complexity and proof complexity. He established connections of these areas to extremal combinatorics, algebra, and mathematical logic. With Rudich he established formal obstacles ("Natural proofs") to attempts at resolving the P vs. NP problem, an important guide to future research. In pure mathematics, he solved entire classes of problems in extremal graph theory via his theory of "flag algebras" and contributed to the field of combinatorial group theory
Last Updated