February 16, 1963 |
Belovo, Russian SFSR, Soviet Union
|Nationality||United States, Russia|
|Institutions||University of Chicago, Steklov Mathematical Institute, Toyota Technological Institute at Chicago|
|Alma mater||Moscow State University|
|Doctoral advisor||Sergei Adian|
|Known for||group theory, logic in computer science, theoretical computer science|
|Notable awards||Nevanlinna Prize (1990)
Gödel Prize (2007)
David P. Robbins Prize (2013)
Aleksandr Aleksandrovich Razborov (Russian: Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist.
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.
- Nevanlinna Prize (1990) for introducing the "approximation method" in proving Boolean circuit lower bounds of some essential algorithmic problems,
- Corresponding Member of the Russian Academy of Sciences (2000)
- 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."
- Andrew MacLeish Distinguished Service Professor (2008) in the Department of Computer Science, University of Chicago.
- 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. 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)
- Avi Wigderson
- Circuit complexity
- Free group
- Natural proofs
- One-way function
- Pseudorandom function family
- Resolution (logic)
- 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". 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.