Home page
Home page
Home page
Russian page
English page
Math-Net.Ru | MMS | Web of Science | Scopus | MathSciNet | zbMATH | Web-mail 

   
 About the Institute
 Staff publications
 Administration
 Academic Council
 Dissertation Councils
 Departments
Staff 
 Chair at MIPT
 Seminars
 Conferences
 Events
 Journals and Books
 In memoriam
 Photogallery
 Charter


    Address
8 Gubkina St. Moscow,
119991, Russia
Tel.: +7(495) 984 81 41
Fax: +7(495) 984 81 39
Web site: www.mi-ras.ru
E-mail: steklov@mi-ras.ru

View Map
Directions

   
Razborov Alexander Alexandrovich
(recent publications)
| by years | scientific publications | by types |



   2022
1. A. A. Razborov, “More about sparse halves in triangle-free graphs”, Sb. Math., 213:1 (2022), 109–128  mathnet  crossref  crossref  adsnasa  adsnasa  isi  scopus
2. Alexander Razborov, “An extremal problem motivated by triangle-free strongly regular graphs”, J. Comb. Theory, Ser. B, 155 (2022), 52–82  mathnet  crossref  scopus;
3. Theodoros Papamakarios, Alexander Razborov, “Space characterizations of complexity measures and size-space trade-offs in propositional proof systems”, Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) (July 4-8, 2022, Paris, France), LIPIcs, 2022, 100:1–100:20
4. Nathan Mull, Shuo Pang, Alexander Razborov, “On CDCL-based proof systems with the ordered decision strategy”, SIAM J. Comput., 51:4 (2022), 1368–1399  mathnet  crossref;

   2021
5. Dhruv Mubayi, Alexander Razborov, “Polynomial to exponential transition in Ramsey theory”, Proc. London Math. Soc., 122:1 (2021), 69-92  mathnet  crossref  mathscinet  isi (cited: 1)  scopus (cited: 1)
6. 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  mathnet  crossref  crossref  mathscinet  adsnasa  adsnasa  isi  elib  scopus
7. 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  mathnet  crossref  crossref  mathscinet  adsnasa  adsnasa  isi
8. Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov, “Clique is hard on average for regular resolution”, Journal of the ACM, 68:4 (2021), 23 , 26 pp.  mathnet  crossref  isi
9. L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021 , 31 pp., arXiv: 2108.06599

   2020
10. L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020 , 84 pp., arXiv: 2012.11773
11. A. Razborov, Kvant, 2020, no. 10, 7–16  mathnet  crossref
12. L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723  mathnet  crossref  crossref  mathscinet  adsnasa  adsnasa  isi (cited: 3)  elib  scopus (cited: 4)
13. 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  mathnet  crossref  isi  scopus;

   2019
14. 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
15. Alexander Razborov, “On Space and Depth in Resolution”, Computational Complexity, 27:3 (2018), 511-559  mathnet  crossref  mathscinet  isi (cited: 5)  scopus (cited: 7)

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

   2016
20. Alexander Razborov, “A new kind of tradeoffs in propositional proof complexity”, Journal of the ACM, 63:2 (2016), 16 , 14 pp.  mathnet  crossref  mathscinet  isi (cited: 11)  elib  scopus (cited: 19)

   2015
21. A. A. Razborov, “Pseudorandom generators hard for $k$-DNF resolution and polynomial calculus resolution”, Ann. of Math. (2), 181:2 (2015), 415–472  mathnet (cited: 3)  crossref  mathscinet  zmath  isi (cited: 15)  elib  scopus (cited: 26)

   2014
22. A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254  mathnet  crossref  crossref  mathscinet  zmath  isi (cited: 2)  elib (cited: 1)  elib (cited: 1)  scopus (cited: 3)
23. A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429  mathnet  crossref  mathscinet  zmath  zmath  isi (cited: 6)  elib (cited: 1)  scopus (cited: 5)

   2013
24. 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  mathnet  crossref  mathscinet  zmath  isi (cited: 64)  elib (cited: 11)  scopus (cited: 71)
25. A. Razborov, “On the Caccetta-Häggkvist conjecture with forbidden subgraphs”, J. Graph Theory, 74:2 (2013), 236–248 , arXiv: 1107.2247  mathnet  crossref  mathscinet  zmath  isi (cited: 15)  elib (cited: 3)  scopus (cited: 16)
26. E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17 , 8 pp.  mathnet  crossref  mathscinet  zmath  scopus (cited: 10)
27. A. A. Razborov, “What is a Flag Algebra?”, Notices Amer. Math. Soc., 60:10 (2013), 1324–1327  crossref  mathscinet  zmath
28. A. Razborov, “Flag algebras: an interim report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232  crossref  mathscinet  scopus (cited: 16)

   2012
29. 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.  mathnet  crossref  zmath  scopus (cited: 17)
30. 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  mathnet  crossref  mathscinet  zmath  isi (cited: 21)  elib (cited: 8)  scopus (cited: 25)
31. A. A. Razborov, Kommunikatsionnaya slozhnost, MTsNMO, 2012 s saita MTsNMO

   2011
32. 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  crossref  mathscinet  zmath  scopus (cited: 3)
33. 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  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  adsnasa  isi  elib
34. 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  mathnet  crossref  mathscinet  isi (cited: 7)  elib  elib  scopus (cited: 8)
35. 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  crossref  mathscinet  zmath  scopus (cited: 1)
36. M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678  crossref  mathscinet  zmath  isi (cited: 14)  elib (cited: 3)  scopus (cited: 18)
37. A. Borodin, T. Pitassi, A. Razborov, “Special Issue In Memory of Misha Alekhnovich. Foreword”, Computational Complexity, 20:4 (2011), 579–590  crossref  mathscinet  zmath  isi  elib  scopus

   2010
38. A. A. Razborov, “On 3-hypergraphs with forbidden 4-vertex configurations”, SIAM J. Discrete Math., 24:3 (2010), 946–963  crossref  mathscinet  zmath  isi (cited: 59)  elib (cited: 31)  scopus (cited: 67)
39. V. Guruswami, J. R. Lee, A. Razborov, “Almost Euclidean subspaces of $\ell^N_1$ via expander codes”, Combinatorica, 30:1 (2010), 47–68  crossref  mathscinet  isi (cited: 7)  elib (cited: 3)  scopus (cited: 9)
40. S. Artemov, V. Diekert, A. Razborov, “Preface”, Symposium on Computer Science (Moscow, June 7–12, 2008), Theory Comput. Syst., 46, no. 4, 2010, 619  crossref  mathscinet  zmath  isi  scopus
41. A. A. Razborov, A. A. Sherstov, “The sign-rank of $\mathrm{AC}^0$”, SIAM J. Comput., 39:5 (2010), 1833–1855  crossref  mathscinet  zmath  isi (cited: 48)  elib (cited: 16)  scopus (cited: 62)
42. F. Eisenbrand, N. Hähnle, A. Razborov, T. Rothvoß, “Diameter of polyhedra: limits of abstraction”, Math. Oper. Res., 35:4 (2010), 786–794  crossref  mathscinet  zmath  isi (cited: 21)  scopus (cited: 28)


Full list of publications
Home page

© Steklov Mathematical Institute of RAS, 2004–2022