A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282
А. А. Разборов, “О квантовой коммуникационной сложности симметрических предикатов”, Изв. РАН. Сер. матем., 67:1 (2003), 159–176; A. A. Razborov, “Quantum communication complexity of symmetric predicates”, Izv. Math., 67:1 (2003), 145–159
A. A. Razborov, S. Rudich, “Natural proofs”, J. Comput. System Sci., 55:1 (1997), 24–35
А. А. Разборов, “Нижние оценки монотонной сложности логического перманента”, Матем. заметки, 37:6 (1985), 887–900; A. A. Razborov, “Lower bounds on monotone complexity of the logical permanent”, Math. Notes, 37:6 (1985), 485–493
А. А. Разборов, “О системах уравнений в свободной группе”, Изв. АН СССР. Сер. матем., 48:4 (1984), 779–832; A. A. Razborov, “On systems of equations in a free group”, Math. USSR-Izv., 25:1 (1985), 115–162
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.
Аlexander Razborov, “Proposition Proof Complexity”, Proceedings of the 8th European Congress of Mathematics (Portoroz, 20–26 June 2021), EMS Press, 2023, 439-464https://ems.press/content/book-files/28311
2022
4.
А. А. Разборов, “Еще раз о разреженных вершинных полуграфах в графах без треугольников”, Матем. сб., 213:1 (2022), 119–140 (цит.: 3) ; 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 fü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 (cited: 1) (cited: 1)
10.
В. С. Атабекян, Л. Д. Беклемишев, В. С. Губа, И. Г. Лысёнок, А. А. Разборов, А. Л. Семенов, “Вопросы алгебры и математической логики. Научное наследие С. И. Адяна”, УМН, 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
11.
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.
12.
L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021 , 31 pp., arXiv: 2108.06599
13.
В. С. Атабекян, Л. Д. Беклемишев, В. М. Бухштабер, С. С. Гончаров, В. С. Губа, Ю. Л. Ершов, В. В. Козлов, И. Г. Лысёнок, С. П. Новиков, Ю. С. Осипов, М. Р. Пентус, В. В. Подольский, А. А. Разборов, В. А. Садовничий, А. Л. Семенов, А. Л. Таламбуца, Д. В. Трещев, Л. Н. Шеврин, “Сергей Иванович Адян (некролог)”, УМН, 76:1(457) (2021), 191–194; 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
L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020 , 84 pp., arXiv: 2012.11773
16.
Л. Н. Корельяно, А. А. Разборов, “Семантические пределы плотных комбинаторных объектов”, УМН, 75:4(454) (2020), 45–152 (цит.: 6) (цит.: 3); L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723 (cited: 3) (cited: 4)
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;
18.
А. Разборов, “Чувствительность булевых функций”, Квант, 2020, № 10, 7–16
2019
19.
А. А. Разборов, “Теория сложности”, Математическая составляющая, 2-е изд., расш. и доп., ред. Н. Н. Андреев, С. П. Коновалов, Н. М. Панюнин, Математические этюды, М., 2019, 262https://book.etudes.ru/toc/complexity/
2018
20.
Alexander Razborov, “On Space and Depth in Resolution”, Computational Complexity, 27:3 (2018), 511-559 (cited: 5) (cited: 7)
2017
21.
Alexander Razborov, “On the width of semi-algebraic proofs and algorithms”, Mathematics of Operation Research, 42:4 (2017), 1106–1134 (cited: 2) (cited: 7)
22.
Oleg Pikhurko, Alexander Razborov, “Asymptotic structure of graphs with the minimum number of triangles”, Comb. Probab. Comput., 26:1 (2017), 138–160 (cited: 16) (cited: 19)
23.
L. N. Coregliano, A. A. Razborov, “On the density of transitive tournaments”, J. Graph Theory, 85:1 (2017), 12–21 , arXiv: 1501.04074 (cited: 12) (cited: 12)
24.
Yuan Li, Alexander Razborov, Benjamin Rossman, “On the $AC^0$ Complexity of Subgraph Isomorphism”, SIAM Journal on Computing, 46:3 (2017), 936–971 (cited: 6) (cited: 10)
2016
25.
Alexander Razborov, “A new kind of tradeoffs in propositional proof complexity”, Journal of the ACM, 63:2 (2016), 16 , 14 pp. (cited: 11) (cited: 19)
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 (cited: 3) (cited: 15) (cited: 26)
2014
27.
А. А. Разборов, “О $(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: 3)
28.
A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429 (cited: 6) (cited: 1) (cited: 5)
2013
29.
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: 64) (cited: 11) (cited: 71)
30.
A. Razborov, “On the Caccetta-Häggkvist conjecture with forbidden subgraphs”, J. Graph Theory, 74:2 (2013), 236–248 , arXiv: 1107.2247 (cited: 15) (cited: 3) (cited: 16)
31.
E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17 , 8 pp. (cited: 10)
32.
A. Razborov, “Flag algebras: an interim report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232 (cited: 16)
33.
А. А. Разборов, “What is a Flag Algebra?”, Notices Amer. Math. Soc., 60:10 (2013), 1324–1327
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. (cited: 17)
35.
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: 21) (cited: 8) (cited: 25)
36.
А. А. Разборов, Коммуникационная сложность, МЦНМО, 2012 с сайта МЦНМО
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 (cited: 3)
38.
А. А. Разборов, “Об интерпретации Фон-Дер-Флаасса экстремальных примеров для $(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)
39.
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)
40.
M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678 (cited: 14) (cited: 3) (cited: 18)
41.
Л. Д. Беклемишев, В. М. Бухштабер, И. Г. Лысëнок, А. А. Мальцев, С. П. Новиков, А. А. Разборов, А. Л. Семëнов, “Сергей Иванович Адян (к восьмидесятилетию со дня рождения)”, УМН, 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
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 (cited: 59) (cited: 31) (cited: 67)
44.
V. Guruswami, J. R. Lee, A. Razborov, “Almost Euclidean subspaces of $\ell^N_1$ via expander codes”, Combinatorica, 30:1 (2010), 47–68 (cited: 7) (cited: 3) (cited: 9)
45.
A. A. Razborov, A. A. Sherstov, “The sign-rank of $\mathrm{AC}^0$”, SIAM J. Comput., 39:5 (2010), 1833–1855 (cited: 48) (cited: 16) (cited: 62)
46.
F. Eisenbrand, N. Hähnle, A. Razborov, T. Rothvoß, “Diameter of polyhedra: limits of abstraction”, Math. Oper. Res., 35:4 (2010), 786–794 (cited: 21) (cited: 28)
47.
S. Artemov, V. Diekert, A. Razborov, “Preface”, Symposium on Computer Science (Moscow, June 7–12, 2008), Theory Comput. Syst., 46, no. 4, 2010, 619
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 (cited: 28) (cited: 9) (cited: 36)
50.
A. A. Razborov, “On the minimal density of triangles in graphs”, Combin. Probab. Comput., 17:4 (2008), 603–618 (cited: 103) (cited: 48) (cited: 115)
2007
51.
A. A. Razborov, S. Yekhanin, “An $\Omega(n^{1/3})$ lower bound for bilinear group-based private information retrieval”, Theory of Computing, 3 (2007), 221–238
52.
A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282 (cited: 130) (cited: 62) (cited: 148)
2006
53.
V. Lifschitz, A. Razborov, “Why are there so many loop formulas?”, ACM Trans. Comput. Log., 7:2 (2006), 261–268 (cited: 59) (cited: 62) (cited: 94)
54.
A. A. Razborov, “The ${\mathsf P}\stackrel{?}{=}{\mathsf NP}$-problem: a view from the 1990s”, Mathematical events of the twentieth century, Springer, Berlin, 2006, 331–346
55.
Л. Д. Беклемишев, И. Г. Лысëнок, А. А. Мальцев, С. П. Новиков, М. Р. Пентус, А. А. Разборов, А. Л. Семëнов, В. А. Успенский, “Сергей Иванович Адян (к 75-летию со дня рождения)”, УМН, 61:3(369) (2006), 179–191 (цит.: 1) ; L. D. Beklemishev, I. G. Lysenok, A. A. Mal'tsev, S. P. Novikov, M. R. Pentus, A. A. Razborov, A. L. Semenov, V. A. Uspenskii, “Sergei Ivanovich Adian (on his 75th birthday)”, Russian Math. Surveys, 61:3 (2006), 575–588
2005
56.
A. A. Razborov, “Foundations of computational complexity theory”, Surveys in modern mathematics, London Math. Soc. Lecture Note Ser., 321, Cambridge Univ. Press, Cambridge, 2005, 186–202
57.
A. A. Razborov, “Guessing more secrets via list decoding”, Internet Math., 2:1 (2005), 21–30 (cited: 1)
58.
А. А. Разборов, “О научном вкладе Б. А. Субботовской”, Матем. просв., 9, Изд-во МЦНМО, М., 2005, 12–15
2004
59.
M. Alekhnovich, E. Ben-Sasson, A. A. Razborov, A. Wigderson, “Pseudorandom generators in propositional proof complexity”, SIAM J. Comput., 34:1 (2004), 67–88 (cited: 35) (cited: 49)
60.
A. A. Razborov, “An upper bound on the threshold quantum decoherence rate”, Quantum Inf. Comput., 4:3 (2004), 222–228 (cited: 12) (cited: 11) (cited: 15)
61.
A. A. Razborov, “Resolution lower bounds for perfect matching principles”, J. Comput. System Sci., 69:1 (2004), 3–27 (cited: 16) (cited: 14) (cited: 25)
62.
A. Razborov, “Feasible Proofs and Computations: Partnership and Fusion”, Automata, Languages and Programming, 31st International Colloquium, ICALP 2004 (Turku, Finland, July 12–16, 2004), Lecture Notes in Computer Science, 3142, Springer, 2004, 8–14
2003
63.
A. Razborov, “Propositional proof complexity”, J. ACM, 50:1 (2003), 80–82 (electronic) (cited: 1)
64.
A. Razborov, “Resolution lower bounds for the weak functional pigeonhole principle”, Logic and complexity in computer science (Créteil, 2001), Theoret. Comput. Sci., 303, no. 1, 2003, 233–243 (cited: 15) (cited: 15) (cited: 25)
65.
А. А. Разборов, “О квантовой коммуникационной сложности симметрических предикатов”, Изв. РАН. Сер. матем., 67:1 (2003), 159–176 (цит.: 62) (цит.: 63); A. A. Razborov, “Quantum communication complexity of symmetric predicates”, Izv. Math., 67:1 (2003), 145–159 (cited: 63) (cited: 45) (cited: 91)
66.
М. В. Алехнович, А. А. Разборов, “Нижние оценки для полиномиального исчисления в случае идеалов, отличных от биномиальных”, Математическая логика и алгебра, Сборник статей. К 100-летию со дня рождения академика Петра Сергеевича Новикова, Тр. МИАН, 242, Наука, М., 2003, 23–43 (цит.: 23) ; M. V. Alekhnovich, A. A. Razborov, “Lower Bounds for Polynomial Calculus: Nonbinomial Case”, Proc. Steklov Inst. Math., 242 (2003), 18–35
2002
67.
A. A. Razborov, “Proof complexity of pigeonhole principles”, Developments in language theory (Vienna, 2001), Lecture Notes in Comput. Sci., 2295, Springer, Berlin, 2002, 110–116
68.
A. Razborov, A. Wigderson, A. Yao, “Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus”, Combinatorica, 22:4 (2002), 555–574 (cited: 6) (cited: 5) (cited: 9)
69.
M. Alekhnovich, E. Ben-Sasson, A. A. Razborov, A. Wigderson, “Space complexity in propositional calculus”, SIAM J. Comput., 31:4 (2002), 1184–1211 (electronic) (cited: 77) (cited: 55) (cited: 102)
2001
70.
М. В. Алехнович, А. А. Разборов, “Нижние оценки для полиномиального исчисления в случае идеалов, отличных от биномиальных”, Докл. АН СССР, 380:3 (2001), 295–297; M. V. Alekhnovich, A. A. Razborov, “Lower bounds for polynomial calculus in the case of nonbinomial ideals”, Dokl. Math., 64:2 (2001), 177–179
А. Разборов, “Theoretical Computer Science: взгляд математика”, Компьютерра, 2001, № 2 электронный вариант
2000
73.
D. Grigoriev, A. Razborov, “Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields”, Appl. Algebra Engrg. Comm. Comput., 10:6 (2000), 465–487 (cited: 49) (cited: 41) (cited: 55)
1999
74.
A. A. Razborov, Vereshchagin Nikolai K., “A property of cross-intersecting families”, Paul Erdős and his mathematics (Budapest, 1999), János Bolyai Math. Soc., Budapest, 1999, 218–220
75.
S. Jukna, A. Razborov, P. Savický, I. Wegener, “On $\mathrm{P}$ versus $\mathrm{NP}\cap\mathrm{CO}$-$\mathrm{NP}$ for decision trees and read-once branching programs”, Comput. Complexity, 8:4 (1999), 357–370 (cited: 18) (cited: 15) (cited: 18)
76.
А. А. Разборов, “О сложности вычислений”, Матем. просв., 3, МЦНМО, М., 1999, 127–141 (цит.: 2)
1998
77.
A. A. Razborov, “Lower bounds for the polynomial calculus”, Comput. Complexity, 7:4 (1998), 291–324 (cited: 63) (cited: 60) (cited: 83)
78.
А. А. Разборов, “О сложности вычислений”, Труды математического центра им. Н. И. Лобачевского, Изд-во «УНИПРЕСС», Казань, 1998, 8–27
79.
S. Jukna, A. Razborov, “Neither reading few bits twice nor reading illegally helps much”, Discrete Appl. Math., 85:3 (1998), 223–238 (cited: 15) (cited: 15) (cited: 18)
80.
Б. С. Кашин, А. А. Разборов, “Новые нижние оценки устойчивости матриц Адамара”, Матем. заметки, 63:4 (1998), 535–540 (цит.: 25) (цит.: 23); B. S. Kashin, A. A. Razborov, “Improved lower bounds on the rigidity of Hadamard matrices”, Math. Notes, 63:4 (1998), 471–475 (cited: 23) (cited: 16) (cited: 17)
1997
81.
A. A. Razborov, S. Rudich, “Natural proofs”, J. Comput. System Sci., 55:1 (1997), 24–35 (cited: 227) (cited: 294)
82.
A. A. Razborov, “On small size approximation models”, The mathematics of Paul Erdős, I, Algorithms Combin., 13, Springer, Berlin, 1997, 385–392
83.
М. М. Арсланов, А. А. Разборов, “Международная школа-конференция “Теория рекурсий и теория сложности” (WRTCT'97)”, УМН, 52:6(318) (1997), 213–214
1996
84.
A. A. Razborov, “Lower bounds for propositional proofs and independence results in bounded arithmetic”, Automata, languages and programming (Paderborn, 1996), Lecture Notes in Comput. Sci., 1099, Springer, Berlin, 1996, 48–62 (cited: 24)
85.
S. Buss, R. Impagliazzo, J. Krajíček, P. Pudlák, A. A. Razborov, J. Sgall, “Proof complexity in algebraic systems and bounded depth Frege systems with modular counting”, Comput. Complexity, 6:3 (1996), 256–298 (cited: 36) (cited: 38) (cited: 63)
86.
Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser, “The future of computational complexity theory: part I.”, SIGACT News, 27:3 (1996), 6-12
1995
87.
J. Håstad, A. Razborov, A. Yao, “On the shrinkage exponent for read-once formulae”, Theoret. Comput. Sci., 141:1-2 (1995), 269–282 (cited: 7) (cited: 9)
88.
A. A. Razborov, “Bounded arithmetic and lower bounds in Boolean complexity”, Feasible mathematics, II (Ithaca, NY, 1992), Progr. Comput. Sci. Appl. Logic, 13, Birkhäuser Boston, Boston, MA, 1995, 344–386
89.
A. A. Razborov, “On systems of equations in free groups”, Combinatorial and geometric group theory (Edinburgh, 1993), London Math. Soc. Lecture Note Ser., 204, Cambridge Univ. Press, Cambridge, 1995, 269–283 (cited: 8)
90.
A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Изв. РАН. Сер. матем., 59:1 (1995), 201–224 (цит.: 12) (цит.: 17); A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Izv. Math., 59:1 (1995), 205–227 (cited: 17) (cited: 15)
1994
91.
A. Razborov, On Provably Disjoint NP-pairs, BRICS server, BRICS, Aarhus, Denmark, 1994
1993
92.
A. Razborov, E. Szemerédi, A. Wigderson, “Constructing small sets that are uniform in arithmetic progressions”, Combin. Probab. Comput., 2:4 (1993), 513–518 (cited: 22)
93.
A. A. Razborov, “On the parameterization of solutions for equations in free groups”, Internat. J. Algebra Comput., 3:3 (1993), 251–273
94.
A. A. Razborov, “An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic”, Arithmetic, proof theory, and computational complexity (Prague, 1991), Oxford Logic Guides, 23, Oxford Univ. Press, New York, 1993, 247–277
95.
A. Borodin, A. Razborov, R. Smolensky, “On lower bounds for read-$k$-times branching programs”, Comput. Complexity, 3:1 (1993), 1–18 (cited: 34) (cited: 102)
96.
A. Razborov, A. Wigderson, “$n^{\Omega(\log n)}$ lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom”, Inform. Process. Lett., 45:6 (1993), 303–307 (cited: 46) (cited: 50)
1992
97.
A. A. Razborov, “On small depth threshold circuits”, Algorithm theory – SWAT '92 (Helsinki, 1992), Lecture Notes in Comput. Sci., 621, Springer, Berlin, 1992, 42–52 (cited: 3) (cited: 35)
A. A. Razborov, “On submodular complexity measures”, Boolean function complexity (Durham, 1990), London Math. Soc. Lecture Note Ser., 169, Cambridge Univ. Press, Cambridge, 1992, 76–83
100.
A. A. Razborov, “On the distributional complexity of disjointness”, Theoret. Comput. Sci., 106:2 (1992), 385–390 (cited: 234) (cited: 305)
101.
A. A. Razborov, “The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear”, Topological, algebraical and combinatorial structures. Frolík's memorial volume, Discrete Math., 108:1-3 (1992), 393–396 (cited: 18) (cited: 21)
1991
102.
A. A. Razborov, “Lower bounds for deterministic and nondeterministic branching programs”, Fundamentals of computation theory (Gosen, 1991), Lecture Notes in Comput. Sci., 529, Springer, Berlin, 1991, 47–60 (cited: 38) (cited: 80)
103.
M. S. Paterson, A. A. Razborov, “The set of minimal braids is co-NP-complete”, J. Algorithms, 12:3 (1991), 393–408 (cited: 27) (cited: 7) (cited: 34)
1990
104.
A. A. Razborov, “Applications of matrix methods to the theory of lower bounds in computational complexity”, Combinatorica, 10:1 (1990), 81–93 (cited: 68) (cited: 10) (cited: 79)
105.
А. А. Разборов, “Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами”, Матем. заметки, 48:6 (1990), 79–90 (цит.: 5) (цит.: 4); A. A. Razborov, “Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits”, Math. Notes, 48:6 (1990), 1226–1234 (cited: 4) (cited: 5)
106.
D. G. Kendall, G. K. Batchelor, N. H. Bingham, W. K. Hayman, J. M. E. Hyland, G. G. Lorentz, H. K. Moffatt, W. Parry, A. A. Razborov, C. A. Robinson, P. Whittle, “Obituary: Andreĭ Nikolaevich Kolmogorov (1903–1987)”, Bull. London Math. Soc., 22:1 (1990), 31–100 (cited: 13)
1989
107.
S. I. Adian, A. A. Razborov, N. N. Repin, “Upper and lower bounds for nilpotency classes of Lie algebras with Engel conditions”, Group theory (Singapore, 1987), de Gruyter, Berlin, 1989, 57–75
108.
A. Razborov, “On the Method of Approximation”, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA., ACM Press, 1989, 167-176
А. А. Разборов, “Формулы ограниченной глубины в базисе $\{\&,\oplus\}$ и некоторые комбинаторные задачи”, Теория сложности и прикладная математическая логика, Проблемы кибернетики, 134, 1988, 149–166
1987
111.
A. A. Razborov, “Lower bounds of the monotone complexity of Boolean functions”, Proceedings of the International Congress of Mathematicians (Berkeley, Calif., 1986), v. 1, 2, Amer. Math. Soc., Providence, RI, 1987, 1478–1487
112.
А. А. Разборов, “Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения”, Матем. заметки, 41:4 (1987), 598–607 (цит.: 6) (цит.: 250); A. A. Razborov, “Lower bounds on the size of bounded depth circuits over a complete basis with logical addition”, Math. Notes, 41:4 (1987), 333–338 (cited: 250) (cited: 28) (cited: 292)
113.
С. И. Адян, А. А. Разборов, “Периодические группы и алгебры Ли”, УМН, 42:2(254) (1987), 3–68 (цит.: 6) (цит.: 3); S. I. Adian, A. A. Razborov, “Periodic groups and Lie algebras”, Russian Math. Surveys, 42:2 (1987), 1–81 (cited: 3) (cited: 3)
А. А. Разборов, “Нижние оценки размера схем ограниченной глубины в базисе $\{\&,\vee,\oplus\}$”, УМН, 41:4(250) (1986), 219–220 (цит.: 1); A. A. Razborov, “Lower estimates of the dimension of schemes of bounded depth in the basis $\{\&,\vee,\oplus\}$”, Russian Math. Surveys, 41:4 (1986), 181–182 (cited: 1) (cited: 1)
1985
116.
А. А. Разборов, “Нижние оценки монотонной сложности некоторых булевых функций”, Докл. АН СССР, 281:4 (1985), 798–801 (цит.: 7) (цит.: 69); A. A. Razborov, “Lower bounds on the monotone complexity of some Boolean functions”, Soviet Math. Doklady, 31 (1985), 354–357 (cited: 69)
117.
А. А. Разборов, “Нижние оценки монотонной сложности логического перманента”, Матем. заметки, 37:6 (1985), 887–900 (цит.: 8) (цит.: 46); A. A. Razborov, “Lower bounds on monotone complexity of the logical permanent”, Math. Notes, 37:6 (1985), 485–493 (cited: 46) (cited: 4) (cited: 56)
1984
118.
А. А. Разборов, “О системах уравнений в свободной группе”, Изв. АН СССР. Сер. матем., 48:4 (1984), 779–832 (цит.: 32) (цит.: 31); A. A. Razborov, “On systems of equations in a free group”, Math. USSR-Izv., 25:1 (1985), 115–162 (cited: 55)
Доклады и лекции в базе данных Math-Net.Ru
1.
Об одном фазовом переходе в теории Рамсея А. А. Разборов Общеинститутский семинар «Математика и ее приложения» Математического института им. В.А. Стеклова Российской академии наук 15 сентября 2022 г. 16:00
2.
Matrix rigidity A. A. Razborov Международная мини-конференция “Approximation and Matrix Complexity” 21 декабря 2021 г. 19:00
Арифметическая комбинаторика. Занятие 3 А. А. Разборов Летняя школа «Современная математика», посвященная памяти Виталия Арнольда, 2017 22 июля 2017 г. 17:15
17.
Арифметическая комбинаторика. Занятие 2 А. А. Разборов Летняя школа «Современная математика», посвященная памяти Виталия Арнольда, 2017 21 июля 2017 г. 15:30
18.
Арифметическая комбинаторика. Лекция 1 А. А. Разборов Летняя школа «Современная математика», посвященная памяти Виталия Арнольда, 2017 20 июля 2017 г. 15:30
Теория сложности доказательств А. А. Разборов Математическая логика, алгебра и вычислимость: двухдневная конференция, посвященная 85-летию С. И. Адяна 18 июля 2016 г. 15:50
2023
Обратная связь: