Nisha Rathode

Alexander Razborov

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Nationality  USA, Russia
Fields  Mathematician

Role  Mathematician
Name  Alexander Razborov
Doctoral advisor  Sergei Adian
Alexander Razborov andrejcommathematicianslargeRazborovAlexanderjpg
Born  February 16, 1963 (age 52) Belovo, Russian SFSR, Soviet Union (1963-02-16)
Institutions  University of Chicago, Steklov Mathematical Institute, Toyota Technological Institute at Chicago
Alma mater  Moscow State University
Known for  group theory, logic in computer science, theoretical computer science
Notable awards  Nevanlinna Prize (1990) Godel Prize (2007) David P. Robbins Prize (2013)
Awards  Nevanlinna Prize, Godel Prize

Education  Moscow State University

Alexander razborov on a combinatorial approach to the hirsch conjecture


Aleksandr Aleksandrovich Razborov (Russian: Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist.

Contents

Alexander Razborov Alexander Razborov receives 2013 Robbins Prize from American

Propositional proof complexity fifteen or so years after alexander razborov


Research

Alexander Razborov httpswwwcsuchicagoedusitescsfilesstyles

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,
  • 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.
  • References

    Alexander Razborov Wikipedia


    Similar Topics
    Phhir
    Nathan Brew
    David Passig
    Topics