Alexander Razborov

From Wikipedia, the free encyclopedia

Alexander Razborov
Born	February 16, 1963(1963-02-16)
Nationality	Russia
Fields	Mathematician
Institutions	Steklov Mathematical Institute
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)

Aleksandr Aleksandrovich Razborov (Russian: Александр Александрович Разборов; born February 16, 1963), sometimes known as Sasha Razborov, is a Russian mathematician and computational theorist who won the Nevanlinna Prize in 1990 for intruducting "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.

Contents 1 Bibliography 2 Notes 3 See also 4 External links

[edit] Bibliography

• A. A. Razborov (1985). "Lower bounds for the monotone complexity of some Boolean functions" (PDF). Soviet Mathematics Doklady 31: 354–357. 
• A. A. Razborov (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). О системах уравнений в свободной группе (PDF) (in Russian), Московский государственный университет.  (PhD thesis)
• A. A. Razborov (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. 
• Alexander A. Razborov (May 1989). "On the method of approximations" (PDF). Proceedings of the 21st Annual ACM Symposium on the Theory of Computing: 167-176. doi:10.1145/73007.73023. 
• A. A. Razborov (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. 
• Alexander A. Razborov, Stephen Rudich (May 1994). "Natural proofs" (PostScript). Proceedings of the 26th Annual ACM Symposium on the Theory of Computing: 204-213. doi:10.1145/195058.195134. 
• Alexander A. Razborov (December 1998). "Lower Bounds for the Polynomial Calculus" (PostScript). Computational Complexity 7 (4): 291–324. doi:10.1007/s000370050013. 
• Alexander A. Razborov (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).

[edit] Notes

[edit] See also

• Algebrization: A New Barrier in Complexity Theory, Scott Aaronson and Avi Wigderson
• Circuit complexity
• Free group
• Natural proofs
• One-way function
• Pseudorandom function family
• Resolution (logic)

[edit] External links

• Alexander Razborov's Home Page.
• All-Russian Mathematical Portal: Persons: Razborov Alexander Alexandrovich.
• DBLP: Alexander A. Razborov.
• International Mathematical Olympiad 1979: Aleksandr Razborov
• 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.

v • d • e Gödel Prize laureates Babai / Goldwasser / Micali / Moran / Rackoff (1993) · Håstad (1994) · Immerman / Szelepcsényi (1995) · Jerrum / Sinclair (1996) · Halpern / Moses (1997) · Toda (1998) · Shor (1999) · Vardi / Wolper (2000) · Arora / Feige / Goldwasser / Lund / Lovász / Motwani / Safra / Sudan / Szegedy (2001) · Sénizergues (2002) · Freund / Shapire (2003) · Herlihy / Saks / Shavit / Zaharoglou (2004) · Alon / Matias / Szegedy (2005) · Agrawal / Kayal / Saxena (2006) · Razborov / Rudich (2007)

v • d • e Nevanlinna Prize winners Tarjan (1982) · Valiant (1986) · Razborov (1990) · Wigderson (1994) · Shor (1998) · Sudan (2002) · Kleinberg (2006)