Quantcast
AR
Russia
228 views this week
Alexander Razborov

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
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.

Research

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.

Awards

  • 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.
The contents of this page are sourced from Wikipedia article. The contents are available under the CC BY-SA 4.0 license.
comments so far.
Comments
Lists
Alexander Razborov is in following lists
View all
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
arrow-left arrow-right arrow-up arrow-down instagram whatsapp myspace quora soundcloud spotify tumblr vk website youtube stumbleupon comments comments pandora gplay iheart tunein pandora gplay iheart tunein itunes