# Alexander Razborov

Russian mathematician

The basics

Quick Facts

Intro | Russian mathematician |

A.K.A. | A.A. Razborov, Aleksandr Aleksandrovich Razborov |

Countries | Russia |

Occupations | Mathematician Computer scientist |

Social | |

Gender | male |

Birth | 16 February 1963 (Belovo) |

Star sign | Aquarius |

Education | MSU Faculty of Mechanics and Mathematics |

The details

Biography

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

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.

- Nevanlinna Prize (1990) for introducing the "approximation method" in proving Boolean circuit lower bounds of some essential algorithmic problems,
- Erdős Lecturer, Hebrew University of Jerusalem, 1998.
- Corresponding member of the Russian Academy of Sciences (2000)
- 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 introducing a new powerful method, flag algebras, to solve problems in extremal combinatorics
- Gödel Prize (2007, with Steven Rudich) for the paper "Natural Proofs."
- Andrew MacLeish Distinguished Service Professor (2008) in the Department of Computer Science, University of Chicago.

comments so far.

Comments

Lists

Alexander Razborov is in following lists

References

http://doi.org/10.1007%2FBF01137685

http://doi.org/10.1007%2FBF01157687

http://doi.org/10.1007%2FBF01240265

http://doi.org/10.1007%2Fs000370050013

http://doi.org/10.1145%2F195058.195134

http://doi.org/10.1145%2F602382.602406

http://doi.org/10.1145%2F73007.73023

http://ams.org/mathscinet/search/publications.html?extend=1&pg1=IID&r=1&s1=212097

http://cs.uchicago.edu/~razborov

http://dblp.uni-trier.de/db/indices/a-tree/r/Razborov:Alexander_A=.html

http://eatcs.org/activities/awards/goedel2007.html