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.
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]
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.
S2CID120875831.
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.
S2CID121744639.
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.
ISBN0897913078.
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.
S2CID120703863.
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.
ISBN0897916638.