Alexander Razborov

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