Home page
Font:
A A A
Color:
A A A
Images:
Special mode Special mode Special mode

Clear mode

  Home page
Home page
Russian page
English page
Math-Net.Ru | 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 Str. Moscow,
119333, Russia
Tel.: +7(495) 984 81 41
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 |



   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  crossref

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

   2024
3. A. A. Razborov, Mat. Pros., 33, MCCME, Moscow, 2024, 151–153  mathnet

   2023
4. 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  mathnet  crossref  mathscinet  isi 1
5. Leonardo N. Coregliano, Alexander A. Razborov, “Natural quasirandomness properties”, Random Structures Algorithms, 63:3 (2023), 624–688  mathnet  crossref  mathscinet 4
6. 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
7. A. A. Razborov, “More about sparse halves in triangle-free graphs”, Sb. Math., 213:1 (2022), 109–128  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  scopus
8. Alexander Razborov, “An extremal problem motivated by triangle-free strongly regular graphs”, J. Comb. Theory, Ser. B, 155 (2022), 52–82  mathnet  crossref  mathscinet  scopus 1
9. 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  mathscinet 1
10. A. A. Razborov, Improved Convergence Guarantees for Shallow Neural Networks, 2022, arXiv: 2212.02323
11. 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 für Informatik, Dagstuhl, Germany, 2022, 100–20  mathnet  crossref  mathscinet;

   2021
12. Dhruv Mubayi, Alexander Razborov, “Polynomial to exponential transition in Ramsey theory”, Proc. London Math. Soc., 122:1 (2021), 69-92  mathnet  crossref  mathscinet  isi  scopus 10
13. 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  zmath  adsnasa  isi  elib  scopus
14. 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  zmath  adsnasa  isi
15. 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 1
16. L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021, 31 pp., arXiv: 2108.06599
17. A. A. Razborov, “Pervoprokhodtsy teoreticheskoi informatiki”, Troitskii variant, Mart 2021, 1-3 https://trv-science.ru/2021/03/pervoproxodcy-teoreticheskoj-informatiki/

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

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

   2017
24. Alexander Razborov, “On the width of semi-algebraic proofs and algorithms”, Mathematics of Operation Research, 42:4 (2017), 1106–1134  mathnet  crossref  mathscinet  isi  scopus 9
25. 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  scopus 22
26. 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  elib  scopus 21
27. 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  scopus 10

   2016
28. 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  elib  scopus 14

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

   2014
30. 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  elib  elib  scopus
31. A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429  mathnet  crossref  mathscinet  zmath  zmath  isi  elib  scopus 13

   2013
32. 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  elib  scopus 93
33. 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  elib  scopus 23
34. E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17, 8 pp.  mathnet  crossref  mathscinet  zmath  scopus 12
35. A. A. Razborov, “What is a Flag Algebra?”, Notices Amer. Math. Soc., 60:10 (2013), 1324–1327  crossref  mathscinet  zmath 5
36. A. Razborov, “Flag algebras: an interim report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232  crossref  mathscinet  scopus 14

   2012
37. 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 14
38. 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  elib  scopus 37
39. A. A. Razborov, Kommunikatsionnaya slozhnost, MTsNMO, 2012 s saita MTsNMO

   2011
40. 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 3
41. 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  isi  elib
42. 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  elib  elib  scopus
43. 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
44. M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678  crossref  mathscinet  zmath  isi  elib  scopus 19
45. 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
46. A. A. Razborov, “On 3-hypergraphs with forbidden 4-vertex configurations”, SIAM J. Discrete Math., 24:3 (2010), 946–963  crossref  mathscinet  zmath  isi  elib  scopus 90
47. 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  elib  scopus 11
48. 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
49. 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  elib  scopus 50
50. 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  scopus 24


Full list of publications
Home page

© Steklov Mathematical Institute of RAS, 2004–2026