Разборов, Александр Александрович

Выпускник московской физико-математической школы № 2 (1980). Окончил механико-математический факультет МГУ (1987). Кандидат физико-математических наук (1987). Доктор физико-математических наук (1991). С 1991 по 2008 год работал в Математическом институте им. В. А. Стеклова РАН. В 2001—2006 году — постоянный член Института перспективных исследований Принстонского университета[3].

С 2008 года — заслуженный профессор в Университете Чикаго (США)[4][5].

26 мая 2000 года избран членом-корреспондентом РАН по Отделению математических наук.

В наиболее известной его работе, написанной совместно со Стивеном Рудичем, он ввёл понятие о «естественных доказательствах», классе стратегий, используемых для доказательства фундаментальных нижних границ в определении вычислительной сложности. В частности, Разборов и Рудич показали, что, в предположении, что определённые виды односторонних функций существуют, такие доказательства не могут дать решение проблемы P = NP, поэтому для того, чтобы эту проблему решить, потребуется разработка новых методов доказательств.

• Золотая медаль Международной математической олимпиады в Лондоне (1979).
• Премия Неванлинны (1990) за «новый приближённый метод решения алгоритмических проблем»[6]
• Премия Гёделя (2007) (совместно со Стивеном Рудичем) за работу о «естественных доказательствах».[7][8]
• Заслуженный профессор (2008) факультета компьютерных наук им. Эндрю МакЛейша в Чикагском университете, США.

• Разборов, А. А. Lower bounds for the monotone complexity of some Boolean functions (англ.) // Доклады Академии наук : journal. — 1985. — Vol. 31. — P. 354—357.
• Разборов, А. А. Нижние оценки монотонной сложности логического перманента (рус.) // Математические заметки Академии Наук СССР : журнал. — 1985. — Июнь (т. 37, № 6). — С. 485—493. — doi:10.1007/BF01157687.
• Разборов, Александр Александрович. О системах уравнений в свободной группе (рус.). — Московский государственный университет, 1987. (Кандидатская диссертация. 32.56MB)
• Разборов, А. А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами (рус.) // Математические заметки Академии Наук СССР : журнал. — 1987. — Апрель (т. 41, № 4). — С. 333—338. — doi:10.1007/BF01137685.
• Razborov, Alexander A. (1989). «On the method of approximations» (PDF. 1.41MB). Proceedings of the 21st Annual ACM Symposium on the Theory of Computing: 167–176. DOI:10.1145/73007.73023.
• Razborov, A. A. Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits (англ.) // Mathematical Notes : journal. — 1990. — December (vol. 48, no. 6). — P. 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: 204–213. DOI:10.1145/195058.195134.
• Razborov, Alexander A. Lower Bounds for the Polynomial Calculus (неопр.) // Computational Complexity. — 1998. — December (т. 7, № 4). — С. 291—324. — doi:10.1007/s000370050013.
• Razborov, Alexander A. Propositional proof complexity (англ.) // Journal of the ACM : journal. — 2003. — January (vol. 50, no. 1). — P. 80—82. — doi:10.1145/602382.602406. (Survey paper for JACM’s 50th anniversary)
• Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.

• Свободная группа
• Односторонняя функция
• Правило резолюций

• Профиль Александра Алексеевича Разборова на официальном сайте РАН
• Разборов Александр Александрович на сайте Всероссийского математического портала
• Персональная страница А. А. Разборова
• 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.