Alexander Razborov Explained

Alexander Razborov
Landscape:	yes
Birth Date:	16 February 1963
Birth Place:	Belovo, Russian SFSR, Soviet Union
Nationality:	American, Russian
Field:	Mathematician
Work Institution:	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
Awards:	Nevanlinna Prize (1990) Gödel Prize (2007) Gödel Lecture (2010) 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. 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]}
• 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

• A. A.. Razborov. Soviet Mathematics - Doklady. 354–357. 31. 1985. Lower bounds for the monotone complexity of some Boolean functions.
• A. A.. Razborov. 10.1007/BF01157687. Mathematical Notes of the Academy of Sciences of the USSR. 485–493. 37. 6. June 1985. Lower bounds on monotone complexity of the logical permanent. 120875831.
• Book: Разборов , Александр Александрович. Московский государственный университет. ru:О системах уравнений в свободной группе. http://www.mi.ras.ru/~razborov/phd.pdf . 1987. ru.

(PhD thesis. 32.56MB)

• A. A.. Razborov. 10.1007/BF01137685. Mathematical Notes of the Academy of Sciences of the USSR. 333–338. 41. 4. April 1987. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. 121744639.
• Alexander A.. Razborov. 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. 10.1145/73007.73023. PDF. 1.41MB. Seattle, Washington, United States. 167–176. May 1989. On the method of approximations. 0897913078. http://www.mi.ras.ru/~razborov/approx.pdf.
• A. A.. Razborov. 10.1007/BF01240265. Mathematical Notes of the Academy of Sciences of the USSR. 1226–1234. 48. 6. December 1990. Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits. 120703863.
• Alexander A.. Razborov. Rudich, Stephen . 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. 10.1145/195058.195134. PostScript. Montreal, Quebec, Canada. 204–213. May 1994. Natural proofs. 0897916638 . http://www.mi.ras.ru/~razborov/int.ps.
• Alexander A.. Razborov. 10.1007/s000370050013. PostScript. Computational Complexity. 291–324. 7. 4. December 1998. Lower Bounds for the Polynomial Calculus. 10.1.1.19.2441. 8130114.
• Alexander A.. Razborov. 10.1145/602382.602406. PostScript. Journal of the ACM. 80–82. 50. 1. January 2003. Propositional proof complexity. 17351318.

(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)

External links

• .
• 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.
  • 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.

Notes and References

1. Web site: International Mathematical Union: Rolf Nevanlinna Prize Winners . dead . https://web.archive.org/web/20071217145338/http://www.mathunion.org/General/Prizes/Nevanlinna/Prizewinners.html . 2007-12-17 .
2. Web site: Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History.
3. Web site: ru. Russian Genealogy Agencies Tree: R. 2008-01-15. https://web.archive.org/web/20071221003151/http://www.rodstvo.ru/R/razin.htm#РАЗБОРОВ. 2007-12-21. dead.
4. Web site: ACM-SIGACT Awards and Prizes: 2007 Gödel Prize.
5. Web site: EATCS: Gödel Prize - 2007. dead. https://web.archive.org/web/20071201092326/http://www.eatcs.org/activities/awards/goedel2007.html. 2007-12-01.
6. Web site: Gödel Lecturers – Association for Symbolic Logic. 2021-11-10. en-US. 2021-11-08. https://web.archive.org/web/20211108212958/https://aslonline.org/other-information/prizes-and-awards/godel-lecturers/. dead.
7. AAAS Fellows Elected. Notices of the American Mathematical Society.