Alexander Razborov
Alexander Razborov | |
|---|---|
| Born | February 16, 1963 |
| Nationality |  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) |
| Scientific career | |
| Fields | Mathematician |
| Institutions | Steklov Mathematical Institute, University of Chicago, 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 who won the Nevanlinna Prize in 1990 for introducing the "approximation method" in proving Boolean circuit lower bounds of some essential algorithmic problems,[1] and the Gödel Prize with Steven Rudich in 2007 for their paper "Natural Proofs."[2][3] His advisor was Sergei Adian. He was elected as a Corresponding Member of the Russian Academy of Sciences on May 26, 2000.[4][5] His Erdős number is 4.[6] 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. Since 2008, he is the Andrew MacLeish Distinguished Service Professor in the Department of Computer Science, University of Chicago.
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. (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.
{{cite journal}}:|format=requires|url=(help); Unknown parameter|month=ignored (help) - Разборов, Александр Александрович (1987). О системах уравнений в свободной группе (PDF) (in Russian). Московский государственный университет. (PhD thesis. 32.56MB)
- Razborov, A. A. (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.
{{cite journal}}:|format=requires|url=(help); Unknown parameter|month=ignored (help) - Razborov, Alexander A. (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.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help); Unknown parameter|month=ignored (help) - Razborov, A. A. (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.
{{cite journal}}:|format=requires|url=(help); Unknown parameter|month=ignored (help) - Razborov, Alexander A. (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.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help); Unknown parameter|coauthors=ignored (|author=suggested) (help); Unknown parameter|month=ignored (help) - Razborov, Alexander A. (1998). "Lower Bounds for the Polynomial Calculus" (PostScript). Computational Complexity. 7 (4): 291–324. doi:10.1007/s000370050013.
{{cite journal}}: Unknown parameter|month=ignored (help) - Razborov, Alexander A. (2003). "Propositional proof complexity" (PostScript). Journal of the ACM. 50 (1): 80–82. doi:10.1145/602382.602406.
{{cite journal}}: Unknown parameter|month=ignored (help) (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".
- ^ "ACM-SIGACT Awards and Prizes: 2007 Gödel Prize".
- ^ "EATCS: Gödel Prize - 2007".
- ^ "Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History".
- ^ "Russian Genealogy Agencies Tree: R" (in Russian).
- ^ "Famous Paths to Paul Erdős: Nevanlinna Prize winners".
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."
- 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.