Alexander Razborov
Template:Short description Script error: No such module "Template wrapper".Script error: No such module "Check for clobbered parameters".
Aleksandr Aleksandrovich Razborov (Template:Langx; 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,[1]
- Erdős Lecturer, Hebrew University of Jerusalem, 1998.
- Corresponding member of the Russian Academy of Sciences (2000)[2][3]
- Gödel Prize (2007, with Steven Rudich) for the paper "Natural Proofs."[4][5]
- 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 Lecturer (2010) with the lecture titled Complexity of Propositional Proofs.[6]
- Andrew MacLeish Distinguished Service Professor (2008) in the Department of Computer Science, University of Chicago.
- Fellow of the American Academy of Arts and Sciences (AAAS) (2020).[7]
Bibliography
- Script error: No such module "Citation/CS1".
- Script error: No such module "Citation/CS1".
- Script error: No such module "citation/CS1". (PhD thesis. 32.56MB)
- Script error: No such module "Citation/CS1".
- Script error: No such module "citation/CS1".
- Script error: No such module "Citation/CS1".
- Script error: No such module "citation/CS1".
- Script error: No such module "Citation/CS1".
- Script error: No such module "Citation/CS1". (Survey paper for JACM's 50th anniversary)
See also
- Avi Wigderson
- Circuit complexity
- Free group
- Natural proofs
- One-way function
- Pseudorandom function family
- Resolution (logic)
Notes
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
Script error: No such module "Check for unknown parameters".
External links
- Template:PAGENAMEBASE at the Mathematics Genealogy ProjectTemplate:EditAtWikidata.
- Alexander Razborov's Home Page.
- All-Russian Mathematical Portal: Persons: Razborov Alexander Alexandrovich.
- Biography sketch in the Toyota Technological Institute at Chicago.
- Curricula Vitae at the Department of Computer Science, University of Chicago.
- DBLP: Alexander A. Razborov.
- Template:IMO results
- The Work of A.A. Razborov – an article by László Lovász in the Proceedings of the International Congress of Mathematicians, Kyoto, Japan, 1990.
Script error: No such module "Navbox". Script error: No such module "Navbox".
Script error: No such module "Authority control".
- Pages with script errors
- 1963 births
- 20th-century Russian mathematicians
- 21st-century Russian mathematicians
- Gödel Prize laureates
- Nevanlinna Prize laureates
- Living people
- Corresponding Members of the Russian Academy of Sciences
- Moscow State University alumni
- Russian computer scientists
- Soviet computer scientists
- Soviet mathematicians
- Theoretical computer scientists
- International Mathematical Olympiad participants
- Fellows of the American Academy of Arts and Sciences
- Russian scientists