Персоналии
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
 
Разборов Александр Александрович

Публикаций: 118 (102)
в MathSciNet: 95 (88)
в zbMATH: 74 (67)
в Web of Science: 68 (62)
в Scopus: 72 (70)
Цитированных статей: 70
Цитирований: 2724
Лекций и докладов: 54

Статистика просмотров:
Эта страница:13193
Страницы публикаций:17008
Полные тексты:5312
Списки литературы:864
член-корреспондент РАН
доктор физико-математических наук (1991)
Специальность ВАК: 01.01.06 (математическая логика, алгебра и теория чисел)
E-mail: , ,
Сайт: https://people.cs.uchicago.edu/~razborov
Ключевые слова: сложность вычислений, экстремальная комбинаторика.
Коды УДК: 510.52, 510.662, 519.712.4, 512.54, 512.554.322, 510.6, 519.85, 519.176, 519.179.1
Коды MSC: 03F20, 03D15, 68Q17, 68Q15

Основные темы научной работы

Теоретическая информация, дискретная математика.

   
Основные публикации:
  1. A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282  crossref  mathscinet  zmath  isi  elib  scopus
  2. А. А. Разборов, “О квантовой коммуникационной сложности симметрических предикатов”, Изв. РАН. Сер. матем., 67:1 (2003), 159–176  mathnet  crossref  mathscinet  zmath  isi; A. A. Razborov, “Quantum communication complexity of symmetric predicates”, Izv. Math., 67:1 (2003), 145–159  crossref  mathscinet  zmath  isi  elib  scopus
  3. A. A. Razborov, S. Rudich, “Natural proofs”, J. Comput. System Sci., 55:1 (1997), 24–35  crossref  mathscinet  zmath  isi  scopus
  4. А. А. Разборов, “Нижние оценки монотонной сложности логического перманента”, Матем. заметки, 37:6 (1985), 887–900  mathnet  mathscinet  zmath  isi; A. A. Razborov, “Lower bounds on monotone complexity of the logical permanent”, Math. Notes, 37:6 (1985), 485–493  crossref  mathscinet  zmath  isi  elib  scopus
  5. А. А. Разборов, “О системах уравнений в свободной группе”, Изв. АН СССР. Сер. матем., 48:4 (1984), 779–832  mathnet  mathscinet  zmath  isi; A. A. Razborov, “On systems of equations in a free group”, Math. USSR-Izv., 25:1 (1985), 115–162  crossref  mathscinet  zmath  scopus

https://www.mathnet.ru/rus/person8770
Список публикаций на Google Scholar
https://zbmath.org/authors/?q=ai:razborov.alexander-a
https://mathscinet.ams.org/mathscinet/MRAuthorID/212097
https://elibrary.ru/author_items.asp?authorid=158
https://www.webofscience.com/wos/author/record/Q-4627-2016
https://www.scopus.com/authid/detail.url?authorId=7004103561

Список публикаций:
| научные публикации | по годам | по типам | по числу цит. | общий список |


Цитирования (Crossref Cited-By Service + Math-Net.Ru)

   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  mathnet  crossref  mathscinet  isi;
2. Leonardo N. Coregliano, Alexander A. Razborov, “Natural quasirandomness properties”, Random Structures Algorithms, 63:3 (2023), 624–688  mathnet  crossref  mathscinet;
3. Аlexander Razborov, “Proposition 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. А. А. Разборов, “Еще раз о разреженных вершинных полуграфах в графах без треугольников”, Матем. сб., 213:1 (2022), 119–140  mathnet  crossref  mathscinet  adsnasa  isi; A. A. Razborov, “More about sparse halves in triangle-free graphs”, Sb. Math., 213:1 (2022), 109–128  crossref  mathscinet  isi  scopus 4
5. 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;
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  mathnet  crossref  mathscinet;
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  mathnet  crossref  mathscinet;

   2021
9. 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 4
10. В. С. Атабекян, Л. Д. Беклемишев, В. С. Губа, И. Г. Лысёнок, А. А. Разборов, А. Л. Семенов, “Вопросы алгебры и математической логики. Научное наследие С. И. Адяна”, УМН, 76:1(457) (2021), 3–30  mathnet  crossref  mathscinet  zmath  adsnasa  isi; 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  crossref  mathscinet  zmath  adsnasa  isi  elib  scopus
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.  mathnet  crossref  isi 1
12. L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021 , 31 pp., arXiv: 2108.06599
13. В. С. Атабекян, Л. Д. Беклемишев, В. М. Бухштабер, С. С. Гончаров, В. С. Губа, Ю. Л. Ершов, В. В. Козлов, И. Г. Лысёнок, С. П. Новиков, Ю. С. Осипов, М. Р. Пентус, В. В. Подольский, А. А. Разборов, В. А. Садовничий, А. Л. Семенов, А. Л. Таламбуца, Д. В. Трещев, Л. Н. Шеврин, “Сергей Иванович Адян (некролог)”, УМН, 76:1(457) (2021), 191–194  mathnet  crossref  mathscinet  zmath  adsnasa  isi; 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  crossref  mathscinet  zmath  adsnasa  isi
14. А. А. Разборов, “Первопроходцы теоретической информатики”, Троицкий вариант, Март 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. Л. Н. Корельяно, А. А. Разборов, “Семантические пределы плотных комбинаторных объектов”, УМН, 75:4(454) (2020), 45–152  mathnet  crossref  mathscinet  zmath  adsnasa  isi; L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723  crossref  mathscinet  zmath  adsnasa  isi  elib  scopus 7
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  mathnet  crossref  isi  scopus; 2
18. А. Разборов, “Чувствительность булевых функций”, Квант, 2020, № 10, 7–16  mathnet  crossref

   2019
19. А. А. Разборов, “Теория сложности”, Математическая составляющая, 2-е изд., расш. и доп., ред. Н. Н. Андреев, С. П. Коновалов, Н. М. Панюнин, Математические этюды, М., 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  mathnet  crossref  mathscinet  isi  scopus 6

   2017
21. 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 7
22. 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 17
23. 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 17
24. 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
25. 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 11

   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  mathnet  crossref  mathscinet  zmath  isi  elib  scopus 21

   2014
27. А. А. Разборов, “О $(3,4)$-проблеме Турана с запрещенными подграфами”, Матем. заметки, 95:2 (2014), 271–281 , arXiv: 1210.4605  mathnet  crossref  mathscinet  zmath  isi  elib; A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254  crossref  mathscinet  isi  elib  scopus 2
28. 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 8

   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  mathnet  crossref  mathscinet  zmath  isi  elib  scopus 77
30. 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 19
31. E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17 , 8 pp.  mathnet  crossref  mathscinet  zmath  scopus 9
32. A. Razborov, “Flag algebras: an interim report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232  crossref  mathscinet  scopus 11
33. А. А. Разборов, “What is a Flag Algebra?”, Notices Amer. Math. Soc., 60:10 (2013), 1324–1327  crossref  mathscinet  zmath 5

   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.  mathnet  crossref  zmath  scopus 14
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  mathnet  crossref  mathscinet  zmath  isi  elib  scopus 29
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  crossref  mathscinet  zmath  scopus 3
38. А. А. Разборов, “Об интерпретации Фон-Дер-Флаасса экстремальных примеров для $(3,4)$-проблемы Турана”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК, М., 2011, 269–290  mathnet  mathscinet  isi  elib; 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  crossref  mathscinet  isi  elib  scopus 11
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  crossref  mathscinet  zmath  scopus
40. M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678  crossref  mathscinet  zmath  isi  elib  scopus 16
41. Л. Д. Беклемишев, В. М. Бухштабер, И. Г. Лысëнок, А. А. Мальцев, С. П. Новиков, А. А. Разборов, А. Л. Семëнов, “Сергей Иванович Адян (к восьмидесятилетию со дня рождения)”, УМН, 66:1(397) (2011), 199–200  mathnet  crossref  mathscinet  zmath  adsnasa  isi  elib; 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  crossref  mathscinet  zmath  adsnasa  isi
42. 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
43. 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 69
44. 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 9
45. 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 47
46. 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 21
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  crossref  mathscinet  zmath  isi  scopus

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

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

   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  crossref  mathscinet  zmath 5
52. A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282  crossref  mathscinet  zmath  isi  elib  scopus 151

   2006
53. V. Lifschitz, A. Razborov, “Why are there so many loop formulas?”, ACM Trans. Comput. Log., 7:2 (2006), 261–268  crossref  mathscinet  zmath  isi  elib  scopus 65
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  crossref  mathscinet  zmath
55. Л. Д. Беклемишев, И. Г. Лысëнок, А. А. Мальцев, С. П. Новиков, М. Р. Пентус, А. А. Разборов, А. Л. Семëнов, В. А. Успенский, “Сергей Иванович Адян (к 75-летию со дня рождения)”, УМН, 61:3(369) (2006), 179–191  mathnet  crossref  mathscinet  zmath  adsnasa  isi  elib; 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  crossref  mathscinet  zmath  adsnasa  isi 1

   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  mathscinet
57. A. A. Razborov, “Guessing more secrets via list decoding”, Internet Math., 2:1 (2005), 21–30  crossref  mathscinet  zmath  scopus 1
58. А. А. Разборов, “О научном вкладе Б. А. Субботовской”, Матем. просв., 9, Изд-во МЦНМО, М., 2005, 12–15  mathnet

   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  crossref  mathscinet  zmath  isi  scopus 41
60. A. A. Razborov, “An upper bound on the threshold quantum decoherence rate”, Quantum Inf. Comput., 4:3 (2004), 222–228  mathscinet  zmath  isi  elib  scopus
61. A. A. Razborov, “Resolution lower bounds for perfect matching principles”, J. Comput. System Sci., 69:1 (2004), 3–27  crossref  mathscinet  zmath  isi  elib  scopus 19
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  crossref  zmath  scopus

   2003
63. A. Razborov, “Propositional proof complexity”, J. ACM, 50:1 (2003), 80–82 (electronic)  crossref  mathscinet  zmath  isi  scopus 2
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  crossref  mathscinet  zmath  isi  elib  scopus 20
65. А. А. Разборов, “О квантовой коммуникационной сложности симметрических предикатов”, Изв. РАН. Сер. матем., 67:1 (2003), 159–176  mathnet  crossref  mathscinet  zmath  isi; A. A. Razborov, “Quantum communication complexity of symmetric predicates”, Izv. Math., 67:1 (2003), 145–159  crossref  mathscinet  zmath  isi  elib  scopus 101
66. М. В. Алехнович, А. А. Разборов, “Нижние оценки для полиномиального исчисления в случае идеалов, отличных от биномиальных”, Математическая логика и алгебра, Сборник статей. К 100-летию со дня рождения академика Петра Сергеевича Новикова, Тр. МИАН, 242, Наука, М., 2003, 23–43  mathnet  mathscinet  zmath; M. V. Alekhnovich, A. A. Razborov, “Lower Bounds for Polynomial Calculus: Nonbinomial Case”, Proc. Steklov Inst. Math., 242 (2003), 18–35  mathscinet  zmath 23

   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  mathscinet  elib
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  crossref  mathscinet  zmath  isi  elib  scopus 8
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)  crossref  mathscinet  zmath  isi  elib  scopus 83

   2001
70. М. В. Алехнович, А. А. Разборов, “Нижние оценки для полиномиального исчисления в случае идеалов, отличных от биномиальных”, Докл. АН СССР, 380:3 (2001), 295–297  mathnet  mathscinet  zmath; M. V. Alekhnovich, A. A. Razborov, “Lower bounds for polynomial calculus in the case of nonbinomial ideals”, Dokl. Math., 64:2 (2001), 177–179  mathscinet  zmath  isi  scopus
71. A. Razborov, Improved Resolution Lower Bounds for the Weak Pigeonhole Principle, Electronic Colloquium on Computational Complexity, 2001  zmath
72. А. Разборов, “Theoretical Computer Science: взгляд математика”, Компьютерра, 2001, № 2 электронный вариант  zmath

   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  crossref  mathscinet  zmath  isi  elib  scopus 35

   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  mathscinet  zmath
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  crossref  mathscinet  zmath  isi  elib  scopus 16
76. А. А. Разборов, “О сложности вычислений”, Матем. просв., 3, МЦНМО, М., 1999, 127–141  mathnet 2

   1998
77. A. A. Razborov, “Lower bounds for the polynomial calculus”, Comput. Complexity, 7:4 (1998), 291–324  crossref  mathscinet  zmath  isi  elib  scopus 70
78. А. А. Разборов, “О сложности вычислений”, Труды математического центра им. Н. И. Лобачевского, Изд-во «УНИПРЕСС», Казань, 1998, 8–27  mathscinet
79. S. Jukna, A. Razborov, “Neither reading few bits twice nor reading illegally helps much”, Discrete Appl. Math., 85:3 (1998), 223–238  crossref  mathscinet  zmath  isi  elib  scopus 16
80. Б. С. Кашин, А. А. Разборов, “Новые нижние оценки устойчивости матриц Адамара”, Матем. заметки, 63:4 (1998), 535–540  mathnet  crossref  mathscinet  zmath  isi; B. S. Kashin, A. A. Razborov, “Improved lower bounds on the rigidity of Hadamard matrices”, Math. Notes, 63:4 (1998), 471–475  crossref  mathscinet  zmath  isi  elib  scopus 28

   1997
81. A. A. Razborov, S. Rudich, “Natural proofs”, J. Comput. System Sci., 55:1 (1997), 24–35  crossref  mathscinet  zmath  isi  scopus 245
82. A. A. Razborov, “On small size approximation models”, The mathematics of Paul Erdős, I, Algorithms Combin., 13, Springer, Berlin, 1997, 385–392  crossref  mathscinet  zmath 1
83. М. М. Арсланов, А. А. Разборов, “Международная школа-конференция “Теория рекурсий и теория сложности” (WRTCT'97)”, УМН, 52:6(318) (1997), 213–214  mathnet  crossref

   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  crossref  mathscinet  zmath  scopus 11
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  crossref  mathscinet  isi  elib  scopus 53
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  crossref 1

   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  crossref  mathscinet  isi  elib  scopus 8
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  mathscinet  zmath
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  mathscinet  zmath  isi
90. A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Изв. РАН. Сер. матем., 59:1 (1995), 201–224  mathnet  mathscinet  zmath  isi; A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Izv. Math., 59:1 (1995), 205–227  crossref  mathscinet  zmath  isi  scopus 34

   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  crossref  mathscinet  zmath  scopus 21
93. A. A. Razborov, “On the parameterization of solutions for equations in free groups”, Internat. J. Algebra Comput., 3:3 (1993), 251–273  crossref  mathscinet  zmath 3
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  mathscinet  zmath
95. A. Borodin, A. Razborov, R. Smolensky, “On lower bounds for read-$k$-times branching programs”, Comput. Complexity, 3:1 (1993), 1–18  crossref  mathscinet  zmath  elib  scopus 91
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  crossref  mathscinet  zmath  isi  scopus 47

   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  crossref  mathscinet  isi  scopus 14
98. Goldmann Mikael, Håstad Johan, Razborov Alexander, “Majority gates vs. general weighted threshold gates”, Comput. Complexity, 2:4 (1992), 277–300  crossref  mathscinet  zmath  elib  scopus 110
99. 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  mathscinet
100. A. A. Razborov, “On the distributional complexity of disjointness”, Theoret. Comput. Sci., 106:2 (1992), 385–390  crossref  mathscinet  zmath  isi  scopus 272
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  crossref  mathscinet  zmath  isi  scopus 23

   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  crossref  mathscinet  isi  scopus 45
103. M. S. Paterson, A. A. Razborov, “The set of minimal braids is co-NP-complete”, J. Algorithms, 12:3 (1991), 393–408  crossref  mathscinet  zmath  isi  elib  scopus 25

   1990
104. A. A. Razborov, “Applications of matrix methods to the theory of lower bounds in computational complexity”, Combinatorica, 10:1 (1990), 81–93  crossref  mathscinet  zmath  isi  elib  scopus 74
105. А. А. Разборов, “Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами”, Матем. заметки, 48:6 (1990), 79–90  mathnet  mathscinet  zmath  isi; A. A. Razborov, “Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits”, Math. Notes, 48:6 (1990), 1226–1234  crossref  mathscinet  zmath  isi  scopus 18
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  crossref  mathscinet  zmath  isi 21

   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  crossref  mathscinet
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
109. А. А. Разборов, Об устойчивых матрицах, МИАН, 1989 отсканированная версия с личного сайта  zmath

   1988
110. А. А. Разборов, “Формулы ограниченной глубины в базисе $\{\&,\oplus\}$ и некоторые комбинаторные задачи”, Теория сложности и прикладная математическая логика, Проблемы кибернетики, 134, 1988, 149–166  mathscinet  zmath

   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  mathscinet
112. А. А. Разборов, “Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения”, Матем. заметки, 41:4 (1987), 598–607  mathnet  mathscinet  zmath  isi; 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  crossref  mathscinet  zmath  isi  elib  scopus 218
113. С. И. Адян, А. А. Разборов, “Периодические группы и алгебры Ли”, УМН, 42:2(254) (1987), 3–68  mathnet  mathscinet  zmath  adsnasa  isi; S. I. Adian, A. A. Razborov, “Periodic groups and Lie algebras”, Russian Math. Surveys, 42:2 (1987), 1–81  crossref  mathscinet  zmath  adsnasa  isi  scopus 6
114. А. А. Разборов, О системах уравнений в свободных группах, канд. дисс., МИАН, Москва, 1987 отсканированная версия с личного сайта

   1986
115. А. А. Разборов, “Нижние оценки размера схем ограниченной глубины в базисе $\{\&,\vee,\oplus\}$”, УМН, 41:4(250) (1986), 219–220  mathnet  mathscinet  zmath  adsnasa  isi; 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  crossref  mathscinet  zmath  adsnasa  isi  scopus 2

   1985
116. А. А. Разборов, “Нижние оценки монотонной сложности некоторых булевых функций”, Докл. АН СССР, 281:4 (1985), 798–801  mathnet  mathscinet  zmath  isi; A. A. Razborov, “Lower bounds on the monotone complexity of some Boolean functions”, Soviet Math. Doklady, 31 (1985), 354–357  mathscinet  zmath  isi 7
117. А. А. Разборов, “Нижние оценки монотонной сложности логического перманента”, Матем. заметки, 37:6 (1985), 887–900  mathnet  mathscinet  zmath  isi; A. A. Razborov, “Lower bounds on monotone complexity of the logical permanent”, Math. Notes, 37:6 (1985), 485–493  crossref  mathscinet  zmath  isi  elib  scopus 47

   1984
118. А. А. Разборов, “О системах уравнений в свободной группе”, Изв. АН СССР. Сер. матем., 48:4 (1984), 779–832  mathnet  mathscinet  zmath  isi; A. A. Razborov, “On systems of equations in a free group”, Math. USSR-Izv., 25:1 (1985), 115–162  crossref  mathscinet  zmath  scopus 49

Доклады и лекции в базе данных Math-Net.Ru
1. Арифметическая комбинаторика. Семинар 3
А. А. Разборов
Летняя школа «Современная математика» имени Виталия Арнольда, 2024
22 июля 2024 г. 11:15   
2. Арифметическая комбинаторика. Семинар 2
А. А. Разборов
Летняя школа «Современная математика» имени Виталия Арнольда, 2024
21 июля 2024 г. 11:15   
3. Арифметическая комбинаторика. Семинар 1
А. А. Разборов
Летняя школа «Современная математика» имени Виталия Арнольда, 2024
20 июля 2024 г. 09:30   
4. О вопросах сходимости и генерализации нейронных сетей малой глубины
А. А. Разборов
Семинар «Математические основы искусственного интеллекта»
19 июня 2024 г. 17:00   
5. Об одном фазовом переходе в теории Рамсея
А. А. Разборов
Общеинститутский семинар «Математика и ее приложения» Математического института им. В.А. Стеклова Российской академии наук
15 сентября 2022 г. 16:00   
6. Matrix rigidity
A. A. Razborov
Международная мини-конференция “Approximation and Matrix Complexity”
21 декабря 2021 г. 19:00   
7. Об одном фазовом переходе в теории Рамсея
А. А. Разборов
Научная сессия МИАН, посвященная подведению итогов 2021 года
24 ноября 2021 г. 17:40   
8. Proof Complexity. Lecture 3
A. A. Razborov
Logical Perspectives 2021: Summer School and Workshop
16 июня 2021 г. 15:30   
9. Proof Complexity. Lecture 2
A. A. Razborov
Logical Perspectives 2021: Summer School and Workshop
15 июня 2021 г. 15:30   
10. Proof Complexity. Lecture 1
A. A. Razborov
Logical Perspectives 2021: Summer School and Workshop
14 июня 2021 г. 15:30   
11. SAT Solvers and Ordered Decision Strategies
A. A. Razborov
«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
27 октября 2020 г. 18:30
12. Limits of Dense Combinatorial Objects
А. А. Разборов
Большой семинар лаборатории комбинаторных и геометрических структур
25 июня 2020 г. 19:00   
13. Теорема Адяна-Рабина
А. А. Разборов
Мемориальная конференция памяти С. И. Адяна
26 мая 2020 г. 15:00   
14. Предельная теория комбинаторных объектов
А. А. Разборов
SIMC Open
25 декабря 2019 г. 13:30   
15. Теория сложности вычислений, занятие 2
А. А. Разборов
Летняя школа «Современная математика» имени Виталия Арнольда, 2019
28 июля 2019 г. 12:45   
16. Теория сложности вычислений, занятие 1
А. А. Разборов
Летняя школа «Современная математика» имени Виталия Арнольда, 2019
27 июля 2019 г. 11:15   
17. Теория сложности вычислений, лекция
А. А. Разборов
Летняя школа «Современная математика» имени Виталия Арнольда, 2019
26 июля 2019 г. 15:30   
18. Полные подграфы в случайных графах и регулярные резолюции
А. А. Разборов
Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая логика»
25 декабря 2018 г. 10:35   
19. Об одном фазовом переходе в теории Рамсея
А. А. Разборов
«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
18 декабря 2018 г. 18:30
20. Арифметическая комбинаторика. Занятие 3
А. А. Разборов
Летняя школа «Современная математика», посвященная памяти Виталия Арнольда, 2017
22 июля 2017 г. 17:15   
21. Арифметическая комбинаторика. Занятие 2
А. А. Разборов
Летняя школа «Современная математика», посвященная памяти Виталия Арнольда, 2017
21 июля 2017 г. 15:30   
22. Арифметическая комбинаторика. Лекция 1
А. А. Разборов
Летняя школа «Современная математика», посвященная памяти Виталия Арнольда, 2017
20 июля 2017 г. 15:30   
23. О невозможности одновременной оптимизации различных мер сложности пропозициональных доказательств
А. А. Разборов
«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
13 декабря 2016 г. 18:30
24. Теория сложности док­азательств
А. А. Разборов
Математическая логика, алгебра и вычислимость: двухдневная конференция, посвященная 85-летию С. И. Адяна
18 июля 2016 г. 15:50   
25. Непрерывная комбинаторика
А. А. Разборов
Узлы и теория представлений
16 июня 2016 г. 17:00
26. Теория сложности доказательств
Александр Разборов
Коллоквиум Факультета компьютерных наук НИУ ВШЭ
14 июня 2016 г. 18:10   
27. Непрерывная комбинаторика
А. А. Разборов
Общеинститутский семинар «Коллоквиум МИАН»
25 декабря 2015 г. 16:00   
28. Сложность доказательств. Занятие 3
А. А. Разборов
Летняя школа «Современная математика», 2015
28 июля 2015 г. 11:15   
29. Сложность доказательств. Занятие 2
А. А. Разборов
Летняя школа «Современная математика», 2015
27 июля 2015 г. 09:30   
30. Сложность доказательств. Занятие 1
А. А. Разборов
Летняя школа «Современная математика», 2015
26 июля 2015 г. 15:30   
31. Непрерывная комбинаторика III
А. А. Разборов
Летняя математическая школа «Алгебра и геометрия», 2014
28 июля 2014 г. 09:30   
32. Непрерывная комбинаторика II
А. А. Разборов
Летняя математическая школа «Алгебра и геометрия», 2014
27 июля 2014 г. 11:30   
33. Непрерывная комбинаторика I
А. А. Разборов
Летняя математическая школа «Алгебра и геометрия», 2014
26 июля 2014 г. 16:30   
34. Непрерывная комбинаторика
А. А. Разборов
Семинар «Глобус» (записи с 2011 года)
26 декабря 2013 г. 15:40   
35. Непрерывная комбинаторика
А. А. Разборов
Межкафедральный семинар МФТИ по дискретной математике
18 декабря 2013 г. 18:30
36. Непрерывная комбинаторика. Лекция 3
А. А. Разборов
Летняя школа «Современная математика», 2013
25 июля 2013 г. 12:45   
37. Непрерывная комбинаторика. Лекция 2
А. А. Разборов
Летняя школа «Современная математика», 2013
24 июля 2013 г. 15:30   
38. Непрерывная комбинаторика. Лекция 1
А. А. Разборов
Летняя школа «Современная математика», 2013
23 июля 2013 г. 15:30   
39. О приближении булевых функций вещественными полиномами малой степени
А. А. Разборов
«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
11 декабря 2012 г. 18:30
40. Экстремальная комбинаторика. Лекция 2
А. А. Разборов
Летняя школа «Современная математика», 2012
26 июля 2012 г. 11:15   
41. Экстремальная комбинаторика. Лекция 1
А. А. Разборов
Летняя школа «Современная математика», 2012
25 июля 2012 г. 09:30   
42. Алгебры флагов
А. А. Разборов
Заседания Санкт-Петербургского математического общества
27 декабря 2011 г. 18:00
43. Теория сложности вычислений. Лекция 3
А. А. Разборов
Летняя школа «Современная математика», 2011
25 июля 2011 г. 12:45   
44. Теория сложности вычислений. Лекция 2
А. А. Разборов
Летняя школа «Современная математика», 2011
24 июля 2011 г. 12:45   
45. Теория сложности вычислений. Лекция 1
А. А. Разборов
Летняя школа «Современная математика», 2011
23 июля 2011 г. 09:30   
46. Алгебраическая сложность. Лекция 2
А. А. Разборов
Летняя школа «Современная математика», 2010
24 июля 2010 г. 09:30   
47. Алгебраическая сложность. Лекция 1
А. А. Разборов
Летняя школа «Современная математика», 2010
23 июля 2010 г. 15:30   
48. Алгебры флагов
А. А. Разборов
Традиционная новогодняя сессия МИАН-ПОМИ, 2009 «Логика и теоретическая информатика»
17 декабря 2009 г. 10:30   
49. Коммуникационная сложность. Лекция 2
А. А. Разборов
Летняя школа «Современная математика», 2009
27 июля 2009 г. 09:30   
50. Коммуникационная сложность. Лекция 1
А. А. Разборов
Летняя школа «Современная математика», 2009
26 июля 2009 г. 15:30   
51. Плотность числа треугольников в графах с известной плотностью рёбер
А. А. Разборов
Семинар отдела дискретной математики МИАН
2 сентября 2008 г. 16:00
52. Обратные задачи арифметической комбинаторики. Лекция вторая
А. А. Разборов
Летняя школа «Современная математика», 2007
29 июля 2007 г. 09:30   
53. Обратные задачи арифметической комбинаторики. Лекция первая
А. А. Разборов
Летняя школа «Современная математика», 2007
28 июля 2007 г. 15:45   
54. Proof Complexity of pigeonhole principles
A. A. Razborov
International Workshop on Logic and Complexity in Computer Science (LCCS'2001)
5 сентября 2001 г. 09:00   

Организации
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024