Alexander Razborov
Alexander Razborov | |
|---|---|
| Born | February 16, 1963 |
| Nationality | United States, Russia |
| Alma mater | Moscow State University |
| Known for | group theory, logic in computer science, theoretical computer science |
| Awards | Nevanlinna Prize (1990) Gödel Prize (2007) David P. Robbins Prize (2013) |
| Scientific career | |
| Fields | Mathematician |
| Institutions | University of Chicago, Steklov Mathematical Institute, Toyota Technological Institute at Chicago |
| Doctoral advisor | Sergei Adian |
Aleksandr Aleksandrovich Razborov (Template:Lang-ru; 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]
- 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."[4][5]
- 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).[6]
Bibliography
- Razborov, A. A. (1985). "Lower bounds for the monotone complexity of some Boolean functions" (PDF). Soviet Mathematics - Doklady. 31: 354–357.
- Razborov, A. A. (June 1985). "Lower bounds on monotone complexity of the logical permanent". Mathematical Notes of the Academy of Sciences of the USSR. 37 (6): 485–493. doi:10.1007/BF01157687.
- Разборов, Александр Александрович (1987). О системах уравнений в свободной группе (PDF) (in Russian). Московский государственный университет. (PhD thesis. 32.56MB)
- Razborov, A. A. (April 1987). "Lower bounds on the size of bounded depth circuits over a complete basis with logical addition". Mathematical Notes of the Academy of Sciences of the USSR. 41 (4): 333–338. doi:10.1007/BF01137685.
- Razborov, Alexander A. (May 1989). "On the method of approximations" (PDF. 1.41MB). Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. Seattle, Washington, United States. pp. 167–176. doi:10.1145/73007.73023.
- Razborov, A. A. (December 1990). "Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits". Mathematical Notes of the Academy of Sciences of the USSR. 48 (6): 1226–1234. doi:10.1007/BF01240265.
- Razborov, Alexander A.; Rudich, Stephen (May 1994). "Natural proofs" (PostScript). Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. Montreal, Quebec, Canada. pp. 204–213. doi:10.1145/195058.195134.
- Razborov, Alexander A. (December 1998). "Lower Bounds for the Polynomial Calculus" (PostScript). Computational Complexity. 7 (4): 291–324. CiteSeerX 10.1.1.19.2441. doi:10.1007/s000370050013.
- Razborov, Alexander A. (January 2003). "Propositional proof complexity" (PostScript). Journal of the ACM. 50 (1): 80–82. doi:10.1145/602382.602406. (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
- ^ "International Mathematical Union: Rolf Nevanlinna Prize Winners". Archived from the original on 2007-12-17.
- ^ "Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History".
- ^ "Russian Genealogy Agencies Tree: R" (in Russian). Archived from the original on 2007-12-21. Retrieved 2008-01-15.
- ^ "ACM-SIGACT Awards and Prizes: 2007 Gödel Prize".
- ^ "EATCS: Gödel Prize - 2007". Archived from the original on 2007-12-01.
- ^ "AAAS Fellows Elected" (PDF). Notices of the American Mathematical Society.
External links
- 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
- MathSciNet: "Items authored by Razborov, A. A."[permanent dead link]
- 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.
| International | |
|---|---|
| Academics | |
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
- Tarski lecturers
- Fellows of the American Academy of Arts and Sciences