M. Alekhnovich, E. Ben-Sasson, A. A. Razborov, A. Wigderson, “Space complexity in propositional calculus”, SIAM J. Comput., 31:4 (2002), 1184–1211 (electronic)
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
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
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
A. A. Razborov, “Lower bounds on monotone complexity of the logical permanent”, Math. Notes, 37:6 (1985), 485–493
20.
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
M. Alekhnovich, E. Ben-Sasson, A. A. Razborov, A. Wigderson, “Pseudorandom generators in propositional proof complexity”, SIAM J. Comput., 34:1 (2004), 67–88
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
M. V. Alekhnovich, A. A. Razborov, “Lower Bounds for Polynomial Calculus: Nonbinomial Case”, Proc. Steklov Inst. Math., 242 (2003), 18–35
29.
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
A. Razborov, E. Szemerédi, A. Wigderson, “Constructing small sets that are uniform in arithmetic progressions”, Combin. Probab. Comput., 2:4 (1993), 513–518
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
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.
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
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
47.
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
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
S. I. Adian, A. A. Razborov, “Periodic groups and Lie algebras”, Russian Math. Surveys, 42:2 (1987), 1–81
59.
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
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
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;
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
68.
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.
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;
72.
Leonardo N. Coregliano, Alexander A. Razborov, “Natural quasirandomness properties”, Random Structures Algorithms, 63:3 (2023), 624–688;
73.
Alexander 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
74.
Alexander Razborov, “An extremal problem motivated by triangle-free strongly regular graphs”, J. Comb. Theory, Ser. B, 155 (2022), 52–82;
75.
Nathan Mull, Shuo Pang, Alexander Razborov, “On CDCL-based proof systems with the ordered decision strategy”, SIAM J. Comput., 51:4 (2022), 1368–1399;
76.
A. A. Razborov, Improved Convergence Guarantees for Shallow Neural Networks, 2022 , arXiv: 2212.02323
77.
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;
78.
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
79.
L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021 , 31 pp., arXiv: 2108.06599
80.
L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020 , 84 pp., arXiv: 2012.11773
81.
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
82.
A. A. Razborov, “A simple proof of Bazzi's theorem”, ACM Transactions on Computation Theory (TOCT), 1:1 (2009), 3 , 5 pp.
83.
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
84.
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
85.
A. A. Razborov, “An upper bound on the threshold quantum decoherence rate”, Quantum Inf. Comput., 4:3 (2004), 222–228
86.
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
87.
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
88.
M. V. Alekhnovich, A. A. Razborov, “Lower bounds for polynomial calculus in the case of nonbinomial ideals”, Dokl. Math., 64:2 (2001), 177–179
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
91.
A. A. Razborov, “O slozhnosti vychislenii”, Trudy matematicheskogo tsentra im. N. I. Lobachevskogo, Izd-vo «UNIPRESS», Kazan, 1998, 8–27
92.
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
93.
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
94.
A. Razborov, On Provably Disjoint NP-pairs, BRICS server, BRICS, Aarhus, Denmark, 1994
95.
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
96.
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
97.
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
98.
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
A. A. Razborov, “Formuly ogranichennoi glubiny v bazise $\{\&,\oplus\}$ i nekotorye kombinatornye zadachi”, Teoriya slozhnosti i prikladnaya matematicheskaya logika, Problemy kibernetiki, 134, 1988, 149–166
101.
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
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
A. A. Razborov, Mat. Pros., 3, MCCME, Moscow, 1999, 127–141
106.
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
107.
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
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
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, 262https://book.etudes.ru/toc/complexity/
112.
A. A. Razborov, Kommunikatsionnaya slozhnost, MTsNMO, 2012 s saita MTsNMO
113.
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
114.
A. Borodin, T. Pitassi, A. Razborov, “Special Issue In Memory of Misha Alekhnovich. Foreword”, Computational Complexity, 20:4 (2011), 579–590
115.
S. Artemov, V. Diekert, A. Razborov, “Preface”, Symposium on Computer Science (Moscow, June 7–12, 2008), Theory Comput. Syst., 46, no. 4, 2010, 619
116.
A. A. Razborov, Mat. Pros., 9, MCCME, Moscow, 2005, 12–15
M. M. Arslanov, A. A. Razborov, “International School-Conference “Recursion Theory and Theory of Complexity” (WRTCT'97)”, Uspekhi Mat. Nauk, 52:6(318) (1997), 213–214
Matrix rigidity A. A. Razborov International Workshop “Approximation and Matrix Complexity” December 21, 2021 19:00
7.
Об одном фазовом переходе в теории Рамсея A. A. Razborov Scientific session of the Steklov Mathematical Institute of RAS dedicated to the results of 2021 November 24, 2021 17:40
8.
Proof Complexity. Lecture 3 A. A. Razborov Logical Perspectives 2021: Summer School and Workshop June 16, 2021 15:30
9.
Proof Complexity. Lecture 2 A. A. Razborov Logical Perspectives 2021: Summer School and Workshop June 15, 2021 15:30
10.
Proof Complexity. Lecture 1 A. A. Razborov Logical Perspectives 2021: Summer School and Workshop June 14, 2021 15:30
Теория сложности доказательств A. A. Razborov Mathematical Logic, Algebra and Computation: A two-day conference dedicated to 85-th anniversary of S. I. Adian July 18, 2016 15:50
Contact us: