Список публикаций

На главную страницу

English page

Об институте

Научная деятельность

Публикации

Правила оформления научных работ

Администрация

Ученый совет

Диссертационные советы

Отделы

Сотрудники

Аспирантура

Научно-образовательный центр

Базовая кафедра МФТИ

Базовая кафедра ФКН ВШЭ

Базовая кафедра матфака НИУ ВШЭ

Противодействие коррупции

Адрес института

Адрес: Россия, 119333, Москва, ул. Губкина, д. 8
Тел.: +7(495) 984 81 41
Сайт: www.mi-ras.ru
E-mail: steklov@mi-ras.ru

Посмотреть карту

Схема проезда

Разборов Александр Александрович
(публикации за последние годы)

по годам

научные публикации

по типам




2026
1.	D. Ingram, A. Razborov, “On the Range of the Permanent of (\pm 1)-Matrices”, Linear Algebra and its Applications, 743 (2026), 271-285

2025
2.	G. Blekherman, A. Raymond, A. Razborov, F. Wei, On Domination Exponents for Pairs of Graphs, 2025, 20 pp., arXiv: 2506.12151

2023
3.	Theodoros Papamakarios, Alexander Razborov, “Space characterizations of complexity measures and size-space trade-offs in propositional proof systems”, J. Comput. Syst. Sci., 137 (2023), 20–36	1 ^[x]
4.	Leonardo N. Coregliano, Alexander A. Razborov, “Natural quasirandomness properties”, Random Structures Algorithms, 63:3 (2023), 624–688	4 ^[x]
5.	Аlexander Razborov, “Propositional Proof Complexity”, Proceedings of the 8th European Congress of Mathematics (Portoroz, 20–26 June 2021), EMS Press, 2023, 439-464 https://ems.press/content/book-files/28311

2022
6.	А. А. Разборов, “Еще раз о разреженных вершинных полуграфах в графах без треугольников”, Матем. сб., 213:1 (2022), 119–140 ; A. A. Razborov, “More about sparse halves in triangle-free graphs”, Sb. Math., 213:1 (2022), 109–128	4 ^[x]
7.	Alexander Razborov, “An extremal problem motivated by triangle-free strongly regular graphs”, J. Comb. Theory, Ser. B, 155 (2022), 52–82	1 ^[x]
8.	Nathan Mull, Shuo Pang, Alexander Razborov, “On CDCL-based proof systems with the ordered decision strategy”, SIAM J. Comput., 51:4 (2022), 1368–1399	1 ^[x]
9.	A. A. Razborov, Improved Convergence Guarantees for Shallow Neural Networks, 2022, arXiv: 2212.02323
10.	Theodoros Papamakarios, Alexander Razborov, “Space characterizations of complexity measures and size-space trade-offs in propositional proof systems”, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), July 4–8, 2022, Paris, France, Leibniz Internat. Proc. in Inform., 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022, 100–20 ;

2021
11.	Dhruv Mubayi, Alexander Razborov, “Polynomial to exponential transition in Ramsey theory”, Proc. London Math. Soc., 122:1 (2021), 69-92	9 ^[x]
12.	В. С. Атабекян, Л. Д. Беклемишев, В. С. Губа, И. Г. Лысёнок, А. А. Разборов, А. Л. Семенов, “Вопросы алгебры и математической логики. Научное наследие С. И. Адяна”, УМН, 76:1(457) (2021), 3–30 ; V. S. Atabekyan, L. D. Beklemishev, V. S. Guba, I. G. Lysenok, A. A. Razborov, A. L. Semenov, “Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian”, Russian Math. Surveys, 76:1 (2021), 1–27
13.	Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov, “Clique is hard on average for regular resolution”, Journal of the ACM, 68:4 (2021), 23, 26 pp.	1 ^[x]
14.	L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021, 31 pp., arXiv: 2108.06599

2020
15.	L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020, 84 pp., arXiv: 2012.11773
16.	Л. Н. Корельяно, А. А. Разборов, “Семантические пределы плотных комбинаторных объектов”, УМН, 75:4(454) (2020), 45–152 ; L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723	14 ^[x]
17.	Nathan Mull, Shuo Pang, Alexander Razborov, “On CDCL-Based Proof Systems with the Ordered Decision Strategy”, Theory and Applications of Satisfiability Testing – SAT 2020, International Conference on Theory and Applications of Satisfiability Testing, Lecture Notes in Comput. Sci., 12178, Springer, Cham, 2020, 149–165 ;	2 ^[x]

2018
18.	Alexander Razborov, “On Space and Depth in Resolution”, Computational Complexity, 27:3 (2018), 511-559	8 ^[x]

2017
19.	Alexander Razborov, “On the width of semi-algebraic proofs and algorithms”, Mathematics of Operation Research, 42:4 (2017), 1106–1134	9 ^[x]
20.	Oleg Pikhurko, Alexander Razborov, “Asymptotic structure of graphs with the minimum number of triangles”, Comb. Probab. Comput., 26:1 (2017), 138–160	20 ^[x]
21.	L. N. Coregliano, A. A. Razborov, “On the density of transitive tournaments”, J. Graph Theory, 85:1 (2017), 12–21, arXiv: 1501.04074	21 ^[x]
22.	Yuan Li, Alexander Razborov, Benjamin Rossman, “On the $AC^0$ Complexity of Subgraph Isomorphism”, SIAM Journal on Computing, 46:3 (2017), 936–971	10 ^[x]

2016
23.	Alexander Razborov, “A new kind of tradeoffs in propositional proof complexity”, Journal of the ACM, 63:2 (2016), 16, 14 pp.	14 ^[x]

2015
24.	A. A. Razborov, “Pseudorandom generators hard for $k$-DNF resolution and polynomial calculus resolution”, Ann. of Math. (2), 181:2 (2015), 415–472	29 ^[x]

2014
25.	А. А. Разборов, “О $(3,4)$-проблеме Турана с запрещенными подграфами”, Матем. заметки, 95:2 (2014), 271–281, arXiv: 1210.4605 ; A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254	3 ^[x]
26.	A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429	11 ^[x]

2013
27.	H. Hatami, J. Hladky, D. Král', S. Norin, A. Razborov, “On the number of pentagons in triangle-free graphs”, J. Combin. Theory Ser. A, 120:3 (2013), 722–732	93 ^[x]
28.	A. Razborov, “On the Caccetta-Häggkvist conjecture with forbidden subgraphs”, J. Graph Theory, 74:2 (2013), 236–248, arXiv: 1107.2247	23 ^[x]
29.	E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17, 8 pp.	12 ^[x]
30.	A. Razborov, “Flag algebras: an interim report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232	14 ^[x]

2012
31.	O. Beyersdorff, N. Galesi, M. Lauria, A. A. Razborov, “Parameterized bounded-depth Frege is not optimal”, ACM Transactions on Computation Theory, 4:3 (2012), 7, 16 pp.	14 ^[x]
32.	H. Hatami, J. Hladký, D. Král, S. Norin, A. Razborov, “Non-three-colourable common graphs exist”, Combin. Probab. Comput., 21:5 (2012), 734–742	37 ^[x]

2011
33.	O. Beyersdorff, N. Galesi, M. Lauria, A. Razborov, “Parameterized bounded-depth Frege is not optimal”, Automata, languages and programming, Part I, Lecture Notes in Comput. Sci., 6755, Springer, Heidelberg, 2011, 630–641	3 ^[x]
34.	А. А. Разборов, “Об интерпретации Фон-Дер-Флаасса экстремальных примеров для $(3,4)$-проблемы Турана”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК, М., 2011, 269–290 ; Alexander A. Razborov, “On the Fon-Der-Flaass interpretation of extremal examples for Turán's $(3,4)$-problem”, Proc. Steklov Inst. Math., 274 (2011), 247–266	11 ^[x]
35.	J. Nordström, A. Razborov, “On minimal unsatisfiability and time-space trade-offs for $k$-DNF resolution”, Automata, languages and programming. Part I, 38th International Colloquium, ICALP 2011 (Zurich, Switzerland, July 4–8, 2011), Lecture Notes in Computer Science, 6755, eds. Luca Aceto, Monika Henzinger, Jiri Sgall, Springer, Heidelberg, 2011, 642–653
36.	M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678	19 ^[x]

2010
37.	A. A. Razborov, “On 3-hypergraphs with forbidden 4-vertex configurations”, SIAM J. Discrete Math., 24:3 (2010), 946–963	89 ^[x]
38.	V. Guruswami, J. R. Lee, A. Razborov, “Almost Euclidean subspaces of $\ell^N_1$ via expander codes”, Combinatorica, 30:1 (2010), 47–68	11 ^[x]
39.	A. A. Razborov, A. A. Sherstov, “The sign-rank of $\mathrm{AC}^0$”, SIAM J. Comput., 39:5 (2010), 1833–1855	50 ^[x]
40.	F. Eisenbrand, N. Hähnle, A. Razborov, T. Rothvoß, “Diameter of polyhedra: limits of abstraction”, Math. Oper. Res., 35:4 (2010), 786–794	24 ^[x]

Полный список публикаций