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.
Alexander Razborov | |
---|---|
Born | |
Nationality | American, Russian |
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 |
Research
editIn 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- 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- Razborov, A. A. (1985). "Lower bounds for the monotone complexity of some Boolean functions" (PDF). Soviet Mathematics - Doklady. 31: 354–357.354-357&rft.date=1985&rft.aulast=Razborov&rft.aufirst=A. A.&rft_id=http://www.mi.ras.ru/~razborov/clique.pdf&rfr_id=info:sid/en.wikipedia.org:Alexander Razborov" class="Z3988">
- 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. S2CID 120875831.485-493&rft.date=1985-06&rft_id=info:doi/10.1007/BF01157687&rft_id=https://api.semanticscholar.org/CorpusID:120875831#id-name=S2CID&rft.aulast=Razborov&rft.aufirst=A. A.&rfr_id=info:sid/en.wikipedia.org:Alexander Razborov" class="Z3988">
- Разборов, Александр Александрович (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. S2CID 121744639.333-338&rft.date=1987-04&rft_id=info:doi/10.1007/BF01137685&rft_id=https://api.semanticscholar.org/CorpusID:121744639#id-name=S2CID&rft.aulast=Razborov&rft.aufirst=A. A.&rfr_id=info:sid/en.wikipedia.org:Alexander Razborov" class="Z3988">
- Razborov, Alexander A. (May 1989). "Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89". Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. Seattle, Washington, United States. pp. 167–176. doi:10.1145/73007.73023. ISBN 0897913078.167-176&rft.date=1989-05&rft_id=info:doi/10.1145/73007.73023&rft.isbn=0897913078&rft.aulast=Razborov&rft.aufirst=Alexander A.&rfr_id=info:sid/en.wikipedia.org:Alexander Razborov" class="Z3988">
- 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. S2CID 120703863.1226-1234&rft.date=1990-12&rft_id=info:doi/10.1007/BF01240265&rft_id=https://api.semanticscholar.org/CorpusID:120703863#id-name=S2CID&rft.aulast=Razborov&rft.aufirst=A. A.&rfr_id=info:sid/en.wikipedia.org:Alexander Razborov" class="Z3988">
- Razborov, Alexander A.; Rudich, Stephen (May 1994). "Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94". Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. Montreal, Quebec, Canada. pp. 204–213. doi:10.1145/195058.195134. ISBN 0897916638.204-213&rft.date=1994-05&rft_id=info:doi/10.1145/195058.195134&rft.isbn=0897916638&rft.aulast=Razborov&rft.aufirst=Alexander A.&rft.au=Rudich, Stephen&rfr_id=info:sid/en.wikipedia.org:Alexander Razborov" class="Z3988">
- 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. S2CID 8130114.291-324&rft.date=1998-12&rft_id=https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.2441#id-name=CiteSeerX&rft_id=https://api.semanticscholar.org/CorpusID:8130114#id-name=S2CID&rft_id=info:doi/10.1007/s000370050013&rft.aulast=Razborov&rft.aufirst=Alexander A.&rft_id=http://www.mi.ras.ru/~razborov/polynom.ps&rfr_id=info:sid/en.wikipedia.org:Alexander Razborov" class="Z3988">
- Razborov, Alexander A. (January 2003). "Propositional proof complexity" (PostScript). Journal of the ACM. 50 (1): 80–82. doi:10.1145/602382.602406. S2CID 17351318.80-82&rft.date=2003-01&rft_id=info:doi/10.1145/602382.602406&rft_id=https://api.semanticscholar.org/CorpusID:17351318#id-name=S2CID&rft.aulast=Razborov&rft.aufirst=Alexander A.&rft_id=http://www.mi.ras.ru/~razborov/jacm50.ps&rfr_id=info:sid/en.wikipedia.org:Alexander Razborov" class="Z3988"> (Survey paper for JACM's 50th anniversary)
See also
editNotes
edit- ^ "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.
- ^ "Gödel Lecturers – Association for Symbolic Logic". Archived from the original on 2021-11-08. Retrieved 2021-11-10.
- ^ "AAAS Fellows Elected" (PDF). Notices of the American Mathematical Society.
External links
edit- 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.