Persons: Razborov Alexander Alexandrovich, List of publications

RUS ENG

Full version

PEOPLE

Razborov Alexander Alexandrovich

Publications

by years

scientific publications

by types




2023
1.	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 ;
2.	Leonardo N. Coregliano, Alexander A. Razborov, “Natural quasirandomness properties”, Random Structures Algorithms, 63:3 (2023), 624–688 ;
3.	Alexander 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
4.	A. A. Razborov, “More about sparse halves in triangle-free graphs”, Sb. Math., 213:1 (2022), 109–128
5.	Alexander Razborov, “An extremal problem motivated by triangle-free strongly regular graphs”, J. Comb. Theory, Ser. B, 155 (2022), 52–82 ;
6.	Nathan Mull, Shuo Pang, Alexander Razborov, “On CDCL-based proof systems with the ordered decision strategy”, SIAM J. Comput., 51:4 (2022), 1368–1399 ;
7.	A. A. Razborov, Improved Convergence Guarantees for Shallow Neural Networks, 2022 , arXiv: 2212.02323
8.	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:1–100:20 ;

2021
9.	Dhruv Mubayi, Alexander Razborov, “Polynomial to exponential transition in Ramsey theory”, Proc. London Math. Soc., 122:1 (2021), 69-92
10.	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
11.	V. S. Atabekyan, L. D. Beklemishev, V. M. Buchstaber, S. S. Goncharov, V. S. Guba, Yu. L. Ershov, V. V. Kozlov, I. G. Lysenok, S. P. Novikov, Yu. S. Osipov, M. R. Pentus, V. V. Podolskii, A. A. Razborov, V. A. Sadovnichii, A. L. Semenov, A. L. Talambutsa, D. V. Treschev, L. N. Shevrin, “Sergei Ivanovich Adian (obituary)”, Russian Math. Surveys, 76:1 (2021), 177–181
12.	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.
13.	L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021 , 31 pp., arXiv: 2108.06599
14.	A. A. Razborov, “Pervoprokhodtsy teoreticheskoi informatiki”, Troitskii variant, Mart 2021, 1-3 https://trv-science.ru/2021/03/pervoproxodcy-teoreticheskoj-informatiki/

2020
15.	L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020 , 84 pp., arXiv: 2012.11773
16.	A. Razborov, Kvant, 2020, no. 10, 7–16
17.	L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723
18.	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 ;

2019
19.	A. A. Razborov, “Teoriya slozhnosti”, Matematicheskaya sostavlyayuschaya, 2-e izd., rassh. i dop., eds. N. N. Andreev, S. P. Konovalov, N. M. Panyunin, Matematicheskie etyudy, M., 2019, 262 https://book.etudes.ru/toc/complexity/

2018
20.	Alexander Razborov, “On Space and Depth in Resolution”, Computational Complexity, 27:3 (2018), 511-559

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

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

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

2014
27.	A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254
28.	A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429

2013
29.	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
30.	A. Razborov, “On the Caccetta-Häggkvist conjecture with forbidden subgraphs”, J. Graph Theory, 74:2 (2013), 236–248 , arXiv: 1107.2247
31.	E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17 , 8 pp.
32.	A. A. Razborov, “What is a Flag Algebra?”, Notices Amer. Math. Soc., 60:10 (2013), 1324–1327
33.	A. Razborov, “Flag algebras: an interim report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232

2012
34.	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.
35.	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
36.	A. A. Razborov, Kommunikatsionnaya slozhnost, MTsNMO, 2012 s saita MTsNMO

2011
37.	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
38.	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
39.	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
40.	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
41.	M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678
42.	A. Borodin, T. Pitassi, A. Razborov, “Special Issue In Memory of Misha Alekhnovich. Foreword”, Computational Complexity, 20:4 (2011), 579–590

2010
43.	A. A. Razborov, “On 3-hypergraphs with forbidden 4-vertex configurations”, SIAM J. Discrete Math., 24:3 (2010), 946–963
44.	V. Guruswami, J. R. Lee, A. Razborov, “Almost Euclidean subspaces of $\ell^N_1$ via expander codes”, Combinatorica, 30:1 (2010), 47–68
45.	S. Artemov, V. Diekert, A. Razborov, “Preface”, Symposium on Computer Science (Moscow, June 7–12, 2008), Theory Comput. Syst., 46, no. 4, 2010, 619
46.	A. A. Razborov, A. A. Sherstov, “The sign-rank of $\mathrm{AC}^0$”, SIAM J. Comput., 39:5 (2010), 1833–1855
47.	F. Eisenbrand, N. Hähnle, A. Razborov, T. Rothvoß, “Diameter of polyhedra: limits of abstraction”, Math. Oper. Res., 35:4 (2010), 786–794

2009
48.	A. A. Razborov, “A simple proof of Bazzi's theorem”, ACM Transactions on Computation Theory (TOCT), 1:1 (2009), 3 , 5 pp.

2008
49.	M. Alekhnovich, A. A. Razborov, “Resolution is not automatizable unless $W[P]$ is tractable”, SIAM J. Comput., 38:4 (2008), 1347–1363
50.	A. A. Razborov, “On the minimal density of triangles in graphs”, Combin. Probab. Comput., 17:4 (2008), 603–618

Full list of publications