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

Выпускник московской физико-математической школы № 2 (1980). Окончил механико-математический факультет МГУ в 1985 году^[2]. Защитил кандидатскую диссертацию по теме «О системах уравнений в свободной группе» в 1987 году (научный руководитель — С. И. Адян)^[3] и докторскую диссертацию по теме «Нижние оценки сложности вычисления булевых функций» в 1991 году^[4][3]; обе диссертации защищены в Математическом институте им. В. А. Стеклова РАН, где в настоящее время является главным научным сотрудником^[5]. В 2001—2006 годах — постоянный член Института перспективных исследований Принстонского университета^[6].

С 2008 года — заслуженный профессор службы Эндрю Маклиша (англ. Andrew MacLeish Distinguished Service Professor) на кафедрах информатики и математики в Университете Чикаго (США)^[7][8].

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

По состоянию на 2025 год входит в состав редакционной коллегии научного издания «Математический сборник».

В 1985 году совершил прорыв в теории сложности, разработав «метод аппроксимации» для доказательства экспоненциальных нижних оценок для монотонных булевых схем.

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

Разработал метод, названный «алгеброй флагов» (англ. flag algebras), который нашёл широкое применение для решения задач в экстремальной комбинаторике. С помощью этого метода, в частности, была решена задача об определении минимально возможного числа треугольников в графе.

Согласно информации с официальной страницы на сайте Чикагского университета, учениками Александра Разборова в разное время были^[9]:

• Алексей Ногин
• Олег Вербицкий (совместно с С. И. Адяном)
• Михаил Алехнович
• Владимир Подольский
• Рагхав Кулкарни (совместно с Дж. Саймоном)
• Пуйа Хатами
• Юань Ли
• Леонардо Нагами Корельяно
• Дилан Кинтана
• Шуо Панг
• Теодорос Папамакариос

• ДеВон Ингрэм

• Золотая медаль Международной математической олимпиады в Лондоне (1979).
• Премия Неванлинны (1990) за «новый приближённый метод решения алгоритмических проблем»^[10].
• Премия Гёделя (2007) (совместно со Стивеном Рудичем) за работу о «естественных доказательствах»^[11][12].
• Заслуженный профессор службы Эндрю Маклиша (англ. Andrew MacLeish Distinguished Service Professor) в Чикагском университете (2008).
• Гёделевская лекция (2010).
• Премия Дэвида П. Роббинса от Американского математического общества (2013).
• Член Американская академия искусств и наук (2020).

• Разборов, А. А. 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. Seattle, Washington (U.S. state), United States. pp. 167—176. DOI:10.1145/73007.73023. Используется устаревший параметр |month= (справка); Неизвестный параметр |Month= (предлагается |month=) (справка на английском)
• 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. Montreal, Quebec, Canada. pp. 204—213. DOI:10.1145/195058.195134. Используется устаревший параметр |month= (справка)
• 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.
• Разборов, А. А. Asymptotic Structure of Graphs with the Minimum Number of Triangles (англ.) // Combinatorics, Probability and Computing. — 2017. — Vol. 26, no. 1. — P. 138—160.
• Разборов, А. А. On the Density of Transitive Tournaments (англ.) // Journal of Graph Theory. — 2017. — Vol. 85, no. 1. — P. 12—21.
• Разборов, А. А. On the AC^0 Complexity of Subgraph Isomorphism (англ.) // SIAM Journal on Computing. — 2017. — Vol. 46, no. 3. — P. 936—971.
• Разборов, А. А. On the Width of Semi-Algebraic Proofs and Algorithms (англ.) // Mathematics of Operations Research. — 2017. — Vol. 42, no. 4. — P. 1106—1134.
• Разборов, А. А. On Space and Depth in Resolution (англ.) // Computational Complexity. — 2018. — Vol. 27, no. 3. — P. 511—559.
• Разборов, А. А. Семантические пределы плотных комбинаторных объектов (рус.) // Успехи математических наук. — 2020. — Т. 75, № 4. — С. 45—152.
• Разборов, А. А. Semantic Limits of Dense Combinatorial Objects (англ.) // Russian Mathematical Surveys. — 2020. — Vol. 75, no. 4. — P. 627—724.
• Разборов, А. А. Clique is hard on average for regular resolution (англ.) // Journal of the ACM. — 2021.
• Разборов, А. А. Polynomial to exponential transition in Ramsey theory (англ.) // Proceedings of the London Mathematical Society. — 2021.
• Разборов, А. А. Вопросы алгебры и математической логики. Научное наследие С. И. Адяна (рус.) // Успехи математических наук. — 2021.
• Разборов, А. А. An Extremal Problem Motivated by Triangle-Free Strongly Regular Graphs (англ.) // Journal of Combinatorial Theory, Series B. — 2022.
• Разборов, А. А. More about sparse halves in triangle-free graphs (англ.) // Sbornik: Mathematics. — 2022.
• Разборов, А. А. On CDCL-based proof systems with the ordered decision strategy (англ.) // SIAM Journal on Computing. — 2022.
• Разборов, А. А. Natural quasirandomness properties (англ.) // Random Structures & Algorithms. — 2023. — Vol. 63.
• Разборов, А. А. Propositional Proof Complexity (англ.) // Proceedings of the 8th European Congress of Mathematics. — 2023.
• Разборов, А. А. Space characterizations of complexity measures and size-space trade-offs in propositional proof systems (англ.) // Journal of Computer and System Sciences. — 2023. — Vol. 137. — P. 20—36.
• Разборов, А. А. Proof Complexity and Beyond (англ.) // Oberwolfach Reports. — 2024.
• Разборов, А. А. On Domination Exponents for Pairs of Graphs (англ.). — 2025.
• Разборов, А. А. On the Range of the Permanent of (±1)-Matrices (англ.). — 2025.