|
|
|
Разборов Александр Александрович
(публикации за последние годы)
|
1. |
В. С. Атабекян, Л. Д. Беклемишев, В. С. Губа, И. Г. Лысёнок, А. А. Разборов, А. Л. Семёнов, “Научное наследие Сергея Ивановича Адяна в области алгебры и математической логики”, УМН (в печати) |
|
2020 |
2. |
Dhruv Mubayi, Alexander Razborov, “Polynomial to exponential transition in Ramsey theory”, Proc. London Math. Soc., 122:1 (2020), 69-92 ; (Published online) |
3. |
Л. Н. Корельяно, А. А. Разборов, “Семантические пределы плотных комбинаторных объектов”, УМН, 75:4(454) (2020), 45–152 , arXiv: 1910.08797 [Л. Н. Корельяно, A. A. Razborov, Uspekhi Mat. Nauk ] |
4. |
Alexander Razborov, An Extremal Problem Motivated by Triangle-Free Strongly Regular Graphs, 2020 , 34 pp., arXiv: 2006.01937 |
5. |
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 ; |
6. |
L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020 , 84 pp., arXiv: 2012.11773 |
7. |
А. Разборов, “Чувствительность булевых
функций”, Квант, 2020, № 10, 7–16 |
|
2019 |
8. |
А. А. Разборов, “Теория сложности”, Математическая составляющая, 2-е изд., расш. и доп., ред. Н. Н. Андреев, С. П. Коновалов, Н. М. Панюнин, Математические этюды, М., 2019, 262 https://book.etudes.ru/toc/complexity/ |
|
2018 |
9. |
Alexander Razborov, “On Space and Depth in Resolution”, Computational Complexity, 27:3 (2018), 511-559 (cited: 3) (cited: 4) |
10. |
Albert Atserias, Ilario Bonacina, Susanna de Rezende, Massimo Lauria, Jakob Nordström, Alexander Razborov, “Clique Is Hard on Average for Regular Resolution”, Journal version to appear in “Journal of the ACM”, Proceedings of the 50th ACM Symposium on Theory of Computing (Los Angeles, CA, USA, June 2018), ACM Press, 2018, 866-877 (cited: 3) |
|
2017 |
11. |
Alexander Razborov, “On the width of semi-algebraic proofs and algorithms”, Mathematics of Operation Research, 42:4 (2017), 1106–1134 (cited: 1) (cited: 2) |
12. |
Oleg Pikhurko, Alexander Razborov, “Asymptotic structure of graphs with the minimum number of triangles”, Comb. Probab. Comput., 26:1 (2017), 138–160 (cited: 12) (cited: 14) |
13. |
L. N. Coregliano, A. A. Razborov, “On the density of transitive tournaments”, J. Graph Theory, 85:1 (2017), 12–21 , arXiv: 1501.04074 (cited: 7) (cited: 8) |
14. |
Yuan Li, Alexander Razborov, Benjamin Rossman, “On the $AC^0$ Complexity of Subgraph Isomorphism”, SIAM Journal on Computing, 46:3 (2017), 936–971 (cited: 4) (cited: 5) |
|
2016 |
15. |
Alexander Razborov, “A new kind of tradeoffs in propositional proof complexity”, Journal of the ACM, 63:2 (2016), 16 , 14 pp. (cited: 10) (cited: 13) |
|
2015 |
16. |
A. A. Razborov, “Pseudorandom generators hard for $k$-DNF resolution and polynomial calculus resolution”, Ann. of Math. (2), 181:2 (2015), 415–472 (cited: 3) (cited: 12) (cited: 16) |
|
2014 |
17. |
А. А. Разборов, “О $(3,4)$-проблеме Турана с запрещенными подграфами”, Матем. заметки, 95:2 (2014), 271–281 , arXiv: 1210.4605 (цит.: 2) (цит.: 2) ; A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254 (cited: 2) (cited: 1) (cited: 2) |
18. |
A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429 (cited: 4) (cited: 1) (cited: 3) |
|
2013 |
19. |
H. Hatami, J. Hladky, D. Král', S. Norin, A. Razborov, “On the number of pentagons in triangle-free graphs”, J. Combin. Theory Ser. A, 120:3 (2013), 722–732 (cited: 50) (cited: 11) (cited: 51) |
20. |
A. Razborov, “On the Caccetta-Häggkvist conjecture with forbidden subgraphs”, J. Graph Theory, 74:2 (2013), 236–248 , arXiv: 1107.2247 (cited: 14) (cited: 3) (cited: 14) |
21. |
E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17 , 8 pp. (cited: 8) |
22. |
А. А. Разборов, “What is a Flag Algebra?”, Notices Amer. Math. Soc., 60:10 (2013), 1324–1327 |
23. |
A. Razborov, “Flag algebras: an interim report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232 (cited: 12) |
|
2012 |
24. |
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. (cited: 11) |
25. |
H. Hatami, J. Hladký, D. Král, S. Norin, A. Razborov, “Non-three-colourable common graphs exist”, Combin. Probab. Comput., 21:5 (2012), 734–742 (cited: 17) (cited: 8) (cited: 19) |
26. |
А. А. Разборов, Коммуникационная сложность, МЦНМО, 2012 с сайта МЦНМО |
|
2011 |
27. |
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 (cited: 3) |
28. |
Л. Д. Беклемишев, В. М. Бухштабер, И. Г. Лысëнок, А. А. Мальцев, С. П. Новиков, А. А. Разборов, А. Л. Семëнов, “Сергей Иванович Адян (к восьмидесятилетию со дня рождения)”, УМН, 66:1(397) (2011), 199–200 ; L. D. Beklemishev, V. M. Buchstaber, I. G. Lysenok, A. A. Mal'tsev, S. P. Novikov, A. A. Razborov, A. L. Semenov, “Sergei Ivanovich Adian (on his eightieth birthday)”, Russian Math. Surveys, 66:1 (2011), 197–198 |
29. |
А. А. Разборов, “Об интерпретации Фон-Дер-Флаасса экстремальных примеров для $(3,4)$-проблемы Турана”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК, М., 2011, 269–290 (цит.: 6) (цит.: 7) ; Alexander A. Razborov, “On the Fon-Der-Flaass interpretation of extremal examples for Turán's $(3,4)$-problem”, Proc. Steklov Inst. Math., 274 (2011), 247–266 (cited: 7) (cited: 8) |
30. |
J. Nordströ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 (cited: 1) |
31. |
M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678 (cited: 10) (cited: 3) (cited: 13) |
32. |
A. Borodin, T. Pitassi, A. Razborov, “Special Issue In Memory of Misha Alekhnovich. Foreword”, Computational Complexity, 20:4 (2011), 579–590 |
|
2010 |
33. |
A. A. Razborov, “On 3-hypergraphs with forbidden 4-vertex configurations”, SIAM J. Discrete Math., 24:3 (2010), 946–963 (cited: 54) (cited: 31) (cited: 57) |
34. |
V. Guruswami, J. R. Lee, A. Razborov, “Almost Euclidean subspaces of $\ell^N_1$ via expander codes”, Combinatorica, 30:1 (2010), 47–68 (cited: 6) (cited: 3) (cited: 7) |
35. |
S. Artemov, V. Diekert, A. Razborov, “Preface”, Symposium on Computer Science (Moscow, June 7–12, 2008), Theory Comput. Syst., 46, no. 4, 2010, 619 |
36. |
A. A. Razborov, A. A. Sherstov, “The sign-rank of $\mathrm{AC}^0$”, SIAM J. Comput., 39:5 (2010), 1833–1855 (cited: 44) (cited: 16) (cited: 51) |
37. |
F. Eisenbrand, N. Hähnle, A. Razborov, T. Rothvoß, “Diameter of polyhedra: limits of abstraction”, Math. Oper. Res., 35:4 (2010), 786–794 (cited: 20) (cited: 25) |
|