Alexander Razborov
Jump to navigation
Jump to search
Alexander Razborov | |
|---|---|
| File:Aleksandr Aleksandrovich Razborov Oberwolfach 2024.jpg Razborov in Oberwolfach, 2024 | |
| Born | February 16, 1963 |
| Alma mater | Moscow State University |
| Known for | group theory, logic in computer science, theoretical computer science |
| Awards |
|
| Scientific career | |
| Fields | Mathematician |
| Institutions | University of Chicago, Steklov Mathematical Institute, Toyota Technological Institute at Chicago |
| Doctoral advisor | Sergei Adian |
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
[edit | edit source]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
[edit | edit source]
- 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
[edit | edit source]- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value). (PhD thesis. 32.56MB)
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value). (Survey paper for JACM's 50th anniversary)
See also
[edit | edit source]- Avi Wigderson
- Circuit complexity
- Free group
- Natural proofs
- One-way function
- Pseudorandom function family
- Resolution (logic)
Notes
[edit | edit source]- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
External links
[edit | edit source]- Alexander Razborov at the Mathematics Genealogy Project.
- 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.
- Alexander Razborov's results at International Mathematical Olympiad
- 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.
Lua error in Module:Authority_control at line 153: attempt to index field 'wikibase' (a nil value).
Categories:
- 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