Alexander Razborov
From Wikipedia, the free encyclopedia
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 2.[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.
[edit] Bibliography
- Razborov, A. A. (1985). "Lower bounds for the monotone complexity of some Boolean functions" (PDF). Soviet Mathematics Doklady 31: 354–357. http://www.mi.ras.ru/~razborov/clique.pdf.
- Razborov, A. A. (June 1985). "Lower bounds on monotone complexity of the logical permanent" (PDF). Mathematical Notes of the Academy of Sciences of the USSR 37 (6): 485–493. doi:10.1007/BF01157687.
- Разборов, Александр Александрович (1987) (in Russian) (PDF). О системах уравнений в свободной группе. Московский государственный университет. http://www.mi.ras.ru/~razborov/phd.pdf. (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" (PDF). 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. http://www.mi.ras.ru/~razborov/approx.pdf.
- Razborov, A. A. (December 1990). "Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits" (PDF). 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. http://www.mi.ras.ru/~razborov/int.ps.
- Razborov, Alexander A. (December 1998). "Lower Bounds for the Polynomial Calculus" (PostScript). Computational Complexity 7 (4): 291–324. doi:10.1007/s000370050013. http://www.mi.ras.ru/~razborov/polynom.ps.
- Razborov, Alexander A. (January 2003). "Propositional proof complexity" (PostScript). Journal of the ACM 50 (1): 80–82. doi:10.1145/602382.602406. http://www.mi.ras.ru/~razborov/jacm50.ps. (Survey paper for JACM's 50th anniversary)
[edit] See also
[edit] External links
| Persondata |
| Name |
Razborov, Alexander |
| Alternative names |
|
| Short description |
|
| Date of birth |
February 16, 1963 |
| Place of birth |
|
| Date of death |
|
| Place of death |
|
Russia
