Steklov Mathematical Institute staff
Steklov Mathematical Institute staff and out-of-staff employees
|
|
|
|
|
|
2027 |
| 1. |
D. S. Shamkanov, “(Non-)well-founded derivations in the provability logic GLP”, The Legacy of A.V. Kuznetsov in Logic, Algebra and the Foundations of Mathematics, Trends in Logic, 71, eds. Alex Citkin, Alexei Muravitsky, Springer Cham, 2027, 1–32 (to appear) https://link.springer.com/book/9783032194596 |
|
2026 |
| 2. |
D. Ingram, A. Razborov, “On the Range of the Permanent of (\pm 1)-Matrices”, Linear Algebra and its Applications, 743 (2026), 271-285 |
| 3. |
Karim F. Shamazov, Alexey L. Talambutsa, “On orbit sets generated by semigroups of one-dimensional affine functions”, Expo. Math., 44:3 (2026), 125765, 11 pp., arXiv: 2507.06875 |
| 4. |
P.Kiyashko, A.Talambutsa, “A simple algorithm for checking equivalence of counting functions on free monoids”, International Journal of Algebra and Computation, 2026, 1–22 (to appear), arXiv: 2407.10569 |
| 5. |
J. P. Aguilera, F. Pakhomov, “The logic of correct models”, Journal of Mathematical Logic, 26:2 (2026), 2550004, 20 pp. https://www.worldscientific.com/doi/abs/10.1142/S0219061325500047?casa_token=X9neTYK_oKsAAAAA:KRrf4ABca80xPxYhQJUTS7604-PZZORRJqYxkHjx-UcoWbiw_3MXroi79Uomn-XG3NXCXnaoCxkb, arXiv: 2402.15382 |
| 6. |
Daniyar Shamkanov, Cyclic proofs in the equational version of Primitive recursive arithmetic, 2026 (Published online), 10 pp., arXiv: https://arxiv.org/abs/2606.07166 |
| 7. |
S. O. Speranski, A. V. Grefenshtein, “On the complexity of first-order logics of probability”, Izv. Math., 90:4 (2026), 754–775 |
| 8. |
S. O. Speranski, “On the closure ordinals of infinitary probabilistic calculi”, Math. Notes, 120:3 (2026), 538–548 |
| 9. |
V. E. Karpov, S. O. Speranskii, “O teorii naturalnykh chisel so standartnym poryadkom i svobodnoi ekvivalentnostyu”, Sibirskii matematicheskii zhurnal, 2026, 1–15 (to appear) |
| 10. |
S. L. Kuznetsov, “Algorithmic complexity of theories with Kleene iteration”, Russian Math. Surveys, 81:1 (2026), 125–188 |
| 11. |
Stepan L. Kuznetsov, “On Lambek grammars with Kleene star”, Distributed Computing and Artificial Intelligence, Special Sessions I, 22nd International Conference (Lille, France, June 25–27, 2025), Lecture Notes in Networks and Systems, 1631, Springer, Cham, 2026, 85–95 |
| 12. |
Max Kanovich, Stepan L. Kuznetsov, Andre Scedrov, “Complexity of equational theories for relational and language action lattices”, Relational and Algebraic Methods in Computer Science, 22nd International Conference, RAMiCS 2026 (Będlewo, Poland, April 7–10, 2026), Lecture Notes in Comput. Sci., 16526, eds. U. Fahrenberg, W. Fussner, L. Santocanale, Springer, 2026, 208–228
|
1
[x]
|
| 13. |
Stepan L. Kuznetsov, “On syntactic concept lattice models for the Lambek calculus and infinitary action logic”, J. Logic Comput., 36:1 (2026), exaf078, 23 pp., arXiv: 2510.24853 |
| 14. |
Stepan L. Kuznetsov, “A survey on language completeness of the Lambek calculus and its extensions”, Computational Linguistics, Information, Reasoning, and AI 2024, Stud. Comput. Intell., 1280, eds. R. Loukanova, Springer, 2026, 25–45 |
| 15. |
Anupam Das, Abhishek De, Stepan L. Kuznetsov, “Undecidability for semirings with fixed points”, 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026) (Lisbon, July 20–23, 2026), Leibniz Internat. Proc. in Inform., 378, eds. F. Pfenning, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2026, 15:1–15:18 |
| 16. |
Stepan L. Kuznetsov, “Complexity of reasoning in Kleene algebra with sum-of-letters hypotheses”, Automated Reasoning, 13th International Conference, IJCAR 2026 (Lisbon, July 26–29, 2026), Part II, Lecture Notes in Artif. Intell., 16689, eds. A. Biere et al., Springer, 2026, 161–177 |
|
2025 |
| 17. |
G. Blekherman, A. Raymond, A. Razborov, F. Wei, On Domination Exponents for Pairs of Graphs, 2025, 20 pp., arXiv: 2506.12151 |
| 18. |
Izv. Math., 89:4 (2025), 758–861 |
| 19. |
S. V. Konyagin, V. Yu. Protasov, A. L. Talambutsa, “Unique expansions in number systems via refinement equations”, Sb. Math., 216:11 (2025), 1614–1627 |
| 20. |
A.Talambutsa, On the word problem for just infinite groups, 2025, 11 pp., arXiv: 2512.24266 |
| 21. |
Lev D. Beklemishev, Fedor N. Pakhomov, “Automatic structures and the problem of natural well-orderings”, Model Theory, Computer Science, and Graph Polynomials: Festschrift in honor of Johann A. Makowsky, Trends in Mathematics, eds. K. Meyer, A. Rabinovich, E. Ravve, A. Villaveces, Birkhäuser, 2025, 91–109, arXiv: 2407.10198
|
1
[x]
|
| 22. |
F. Pakhomov, G. Solda, “On Nash-Williams' Theorem regarding sequences with finite range”, Transactions of the AMS, 2025, 30 (to appear), arXiv: 2405.13842 |
| 23. |
Hanul Jeon, Patrick Lutz, Fedor Pakhomov, James Walsh, Ranking theories via encoded β-models, 2025, 21 pp., arXiv: 2503.20470 |
| 24. |
Fedor Pakhomov, Giovanni Soldà, Generalized Higman's Theorem and iterated ideals, 2025, 22 pp., arXiv: 2512.07685 |
| 25. |
Izv. Math., 89:2 (2025), 399–421 |
| 26. |
L. D. Beklemishev, D. S. Shamkanov, I. N. Smirnov, “Fragments of arithmetic and cyclic proofs”, Sb. Math., 216:10 (2025), 1339–1362 |
| 27. |
D. Shamkanov, (Non-)well-founded derivations in the provability logic GLP, 2025, 37 pp., arXiv: 2504.01388 |
| 28. |
Stanislav O. Speranski, “Sharpening complexity results in quantified probability logic”, Log. J. IGPL, 33:3 (2025), jzae114, 21 pp.
|
7
[x]
|
| 29. |
Stanislav O. Speranski, “An ‘elementary’ perspective on reasoning about probability spaces”, Log. J. IGPL, 33:2 (2025), jzae042, 23 pp.
|
5
[x]
|
| 30. |
S. O. Speranski, “On the decision problem for quantified probability logics”, Izv. Math., 89:3 (2025), 609–627 |
| 31. |
V. E. Karpov, S. O. Speranski, “On hereditarily undecidable fragments of basic elementary theories”, Math. Notes, 118:1 (2025), 95–107 |
| 32. |
Stepan L. Kuznetsov, Tikhon Pshenitsyn, Stanislav O. Speranski, “Reasoning from hypotheses in *-continuous action lattices”, J. Symb. Log., 2025, 1–39 (Published online), arXiv: 2408.02118
|
1
[x]
|
| 33. |
S. O. Speranski, “On Fitting’s modification of Kripke’s theory of truth”, Doklady Mathematics, 2025 (to appear) |
| 34. |
S. N. Artemov, L. D. Beklemishev, S. S. Goncharov, Yu. L. Ershov, S. P. Odintsov, V. V. Rybakov, S. O. Speranski, V. B. Shehtman, V. F. Yun, “Larisa L'vovna Maksimova (obituary)”, Russian Math. Surveys, 80:3 (2025), 533–536 |
| 35. |
A. L. Semenov, M. A. Babenko, A. Ya. Belov, N. K. Vereshchagin, M. E. Vishnikin, E. E. Zolin, V. N. Krupski, S. L. Kuznetsov, V. A. Lyubetskii, A. A. Onoprienko, M. R. Pentus, S. F. Soprunov, A. A. Sorokin, V. B. Shehtman, T. L. Yavorskaya, “Chair of Mathematical Logic and Theory of Algorithms”, Moscow University Mathematics Bulletin, 80:1 (2025), 23–33 |
| 36. |
Mikhail Valinkin, Stepan L. Kuznetsov, “Relational models for the Lambek calculus with local contraction subexponentials”, J. Logic Comput., 35:4 (2025), exaf030, 21 pp. |
|
2024 |
| 37. |
A. A. Razborov, Mat. Pros., 33, MCCME, Moscow, 2024, 151–153 |
| 38. |
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii, “Logical Languages Accepted by Transformer Encoders with Hard Attention”, The Twelfth International Conference on Learning Representations, {ICLR} 2024, Vienna, Austria, May 7-11, 2024, OpenReview.net, 2024, 1-11 https://openreview.net/forum?id=gbrHZq07mq |
| 39. |
Vladimir V. Podolskii and Dmitrii Sluch, “One-Way Communication Complexity of Partial XOR Functions”, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, LIPIcs, 2024, 116, 16 pp. |
| 40. |
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii, “Towards Simpler Sorting Networks and Monotone Circuits for Majority”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK, LIPIcs, 2024, 50, 18 pp. |
| 41. |
Vladimir Podolskii, Victor Selivanov, “Complexity Aspects of the Extension of Wagner's Hierarchy to k-Partitions”, Proceedings 14th International Workshop on
Non-Classical Models of Automata and Applications, Electronic Proceedings in Theoretical Computer Science, 407, Open Publishing Association, 2024, 186–197 |
| 42. |
Alexander I. Bufetov, Gabriel Nivasch, Fedor Pakhomov, “Generalized fusible numbers and their ordinals”, Ann. Pure Appl. Logic, 175 (2024), 103355, 25 pp.
|
1
[x]
|
| 43. |
Juvenal Murwanashyaka, Fedor Pakhomov, Albert Visser, “There are no minimal essentially undecidable theories”, J. Logic Comput., 34:6 (2024), 1159–1171
|
5
[x]
|
| 44. |
J. P. Aguilera, F. Pakhomov, A. Weiermann, “Functorial fast-growing hierarchies”, Forum Math. Sigma, 12 (2024), 15, 16 pp.
|
2
[x]
|
| 45. |
Anton Freund, Fedor Pakhomov, Giovanni Soldà, “The logical strength of minimal bad arrays”, Proc. Amer. Math. Soc., 152 (2024), 4993–5005, arXiv: 2304.00278
|
2
[x]
|
| 46. |
Daniyar Shamkanov, “On algebraic and topological semantics of the modal logic of common knowledge $S4^C_I$”, Log. J. IGPL, 32:1 (2024), 164–179, arXiv: 2111.05676
|
1
[x]
|
| 47. |
Daniyar Shamkanov, “On structural proof theory of the modal logic $K^+$ extended with infinitary derivations”, Log. J. IGPL, 2024, jzae121, 46 pp., arXiv: 2310.10309
|
3
[x]
|
| 48. |
A. V. Grefenshtein, S. O. Speranski, “On the quantified version of the Belnap–Dunn modal logic”, Sb. Math., 215:3 (2024), 323–354 |
| 49. |
S. O. Speranskii, Teoriya vnutrennikh mnozhestv: Aksiomaticheskii podkhod k nestandartnomu analizu, Lektsii letnei shkoly «Sovremennaya matematika», Izdatelstvo MTsNMO, Moskva, 2024, 32 pp. preprint |
| 50. |
S. L. Kuznetsov, “Algorithmic complexity for theories of commutative Kleene algebras”, Izv. Math., 88:2 (2024), 236–269 |
| 51. |
Stepan L. Kuznetsov, “Syntactic concept lattice models for infinitary action logic”, Logic, Language, Information, and Computation, 30th International Workshop, WoLLIC 2024 (Bern, Switzerland, June 10–13, 2024), Lecture Notes in Comput. Sci., 14672, Springer, Cham, 2024, 93–107
|
1
[x]
|
| 52. |
S. L. Kuznetsov, Algoritmicheskie voprosy dlya substrukturnykh logik s iteratsiei Klini, Diss. … dokt. fiz.-matem. nauk, Matematicheskii institut im. V. A. Steklova RAN, Moskva, 2024, 266 pp. (.pdf) |
| 53. |
S. L. Kuznetsov, “Strong conservativity and completeness for fragments of infinitary action logic”, Sib. elektron. matem. izv., 21:2 (2024), 789–809
|
2
[x]
|
|
2023 |
| 54. |
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
|
1
[x]
|
| 55. |
Leonardo N. Coregliano, Alexander A. Razborov, “Natural quasirandomness properties”, Random Structures Algorithms, 63:3 (2023), 624–688
|
4
[x]
|
| 56. |
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 |
| 57. |
A. L. Talambutsa, T. Hartnick, “Efficient computations with counting functions on free groups and free monoids”, Sb. Math., 214:10 (2023), 1458–1499 |
| 58. |
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii, “Constant-Depth Sorting Networks”, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Leibniz Internat. Proc. in Inform., 251, 2023, 43, 19 pp. |
| 59. |
J. P. Aguilera, F. Pakhomov, “The $\Pi^1_2$ consequences of a theory”, J. London Math. Soc., 107:3 (2023), 1045–1073, arXiv: 2109.11652
|
2
[x]
|
| 60. |
Fedor Pakhomov, James Walsh, “Reducing $\omega$-model reflection to iterated syntactic reflection”, J. Math. Log., 23:2 (2023), 2250001, 38 pp.
|
2
[x]
|
| 61. |
Anton Freund, Alberto Marcone, Fedor Pakhomov, Giovanni Soldà, Provable better quasi orders, 2023, 3 pp., arXiv: 2305.01066 |
| 62. |
J. P. Aguilera, F. Pakhomov, A. Weiermann, “Modern perspectives in Proof Theory”, Philos. Trans. R. Soc. A, 381 (2023), 20220020, 11 pp. |
| 63. |
J. P. Aguilera, F. Pakhomov, “The spectrum of $\Pi^1_3$-soundness”, Philos. Trans. R. Soc. A, 381 (2023), 20220013, 18 pp.
|
1
[x]
|
| 64. |
Stepan L. Kuznetsov, Stanislav O. Speranski, “Infinitary action logic with multiplexing”, Studia Logica, 111:2 (2023), 251–280
|
7
[x]
|
| 65. |
S. O. Speranski, “Elementary invariants for quantified probability logic”, Doklady Mathematics, 107 (2023), 93–96 |
| 66. |
Stepan L. Kuznetsov, “Commutative action logic”, J. Logic Comput., 33:6 (2023), 1427–1462, arXiv: 2102.11639
|
4
[x]
|
| 67. |
Stepan L. Kuznetsov, “Complexity of the Lambek calculus and its extensions”, Logic and Algorithms in Computational Linguistics 2021, LACompLing2021, Stud. Comput. Intell., 1081, Springer, Cham, 2023, 1–29 |
| 68. |
Stepan L. Kuznetsov, “Proof disbalancing for proving complexity results: towards infinitary focusing”, The Proof Society Summer School and Workshop 2023. Booklet of Abstracts (Barcelona, July 10–14, 2023), University of Barcelona, 2023, 69–72 (pdf) |
| 69. |
Eben Blaisdell, Max Kanovich, Stepan L. Kuznetsov, Elaine Pimentel, Andre Scedrov, “Explorations in subexponential non-associative non-commutative linear logic”, Proceedings Modalities in substructural logics: Applications at the interfaces of logic, language and computation (AMSLO 2023), Ljubljana, Slovenia, August 7-8, 2023, Electron. Proc. Theor. Comput. Sci., 381, Open Publishing Association, 2023, 4–19, arXiv: 2308.05537v1 |
| 70. |
Stepan L. Kuznetsov, “On the complexity of reasoning in Kleene algebra with commutativity conditions”, Theoretical Aspects of Computing – ICTAC 2023, Lima, Peru, December 4–8, 2023, Lecture Notes in Comput. Sci., 14446, Springer, Cham, 2023, 83–99
|
8
[x]
|
| 71. |
Stepan L. Kuznetsov, “Relational models for the Lambek calculus with intersection and constants”, Log. Methods Comput. Sci., 19:4 (2023), 32, 27 pp., arXiv: 2210.00654
|
3
[x]
|
|
2022 |
| 72. |
A. A. Razborov, “More about sparse halves in triangle-free graphs”, Sb. Math., 213:1 (2022), 109–128 |
| 73. |
Alexander Razborov, “An extremal problem motivated by triangle-free strongly regular graphs”, J. Comb. Theory, Ser. B, 155 (2022), 52–82
|
1
[x]
|
| 74. |
Nathan Mull, Shuo Pang, Alexander Razborov, “On CDCL-based proof systems with the ordered decision strategy”, SIAM J. Comput., 51:4 (2022), 1368–1399
|
1
[x]
|
| 75. |
A. A. Razborov, Improved Convergence Guarantees for Shallow Neural Networks, 2022, arXiv: 2212.02323 |
| 76. |
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 ; |
| 77. |
Laurent Bartholdi, Thorsten Groth, Igor Lysenok, “Commutator width in the first Grigorchuk group”, Groups Geom. Dyn., 16:2 (2022), 493–522
|
4
[x]
|
| 78. |
Alexander Kolpakov, Alexey Talambutsa, “On free semigroups of affine maps on the real line”, Proc. Amer. Math. Soc., 150:6 (2022), 2301–2307, arXiv: 2105.09387
|
3
[x]
|
| 79. |
Jean-Camille Birget, Alexey L. Talambutsa, “The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups”, Int. J. Algebra Comput., 32:6 (2022), 1261–1274, arXiv: 2112.02408 |
| 80. |
Alexander Kolpakov, Alexey Talambutsa, “Growth rates of Coxeter groups and Perron numbers”, Int. Math. Res. Not. IMRN, 2022:19 (2022), 14675–14696, arXiv: 1912.05608 |
| 81. |
Anastasiya Chistopolskaya, Vladimir V. Podolskii, “On the Decision Tree Complexity of Threshold Functions”, Theory Comput. Syst., 66 (2022), 1074–1098
|
2
[x]
|
| 82. |
Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir Podolskii, Michael Zakharyaschev, “A tetrachotomy of ontology-mediated queries with a covering axiom”, Artif. Intell., 309 (2022), 103738, 46 pp.
|
1
[x]
|
| 83. |
Vladimir Podolskii, Nikolay V. Proskurin, “Polynomial threshold functions for decision lists”, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz Internat. Proc. in Inform., 248, 2022, 52:1–52:12 |
| 84. |
Alexander Kozachinskiy, Vladimir Podolskii, “Multiparty Karchmer–Wigderson games and threshold circuits”, Theory Comput., 18 (2022), 15, 33 pp. |
| 85. |
S. O. Speranski, F. N. Pakhomov, “On the coprimeness relation from the viewpoint of monadic second-order logic”, Izv. Math., 86:6 (2022), 1225–1239 |
| 86. |
Lev D. Beklemishev, Fedor N. Pakhomov, “Reflection algebras and conservation results for theories of iterated truth”, Ann. Pure Appl. Logic, 173:5 (2022), 103093, 41 pp.
|
11
[x]
|
| 87. |
Fedor Pakhomov, Albert Visser, “Finitely axiomatized theories lack self-comprehension”, Bull. Lond. Math. Soc., 54:6 (2022), 2513–2531, arXiv: 2109.02548
|
4
[x]
|
| 88. |
Stepan L. Kuznetsov, Stanislav O. Speranski, “Infinitary action logic with exponentiation”, Annals of Pure and Applied Logic, 173:2 (2022), 103057, 29 pp., arXiv: 2001.06863
|
15
[x]
|
| 89. |
S. O. Speranski, “Some remarks on Došen's logic N and its extensions”, Sib. elektron. matem. izv., 19:2 (2022), 562–577 |
| 90. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “Language models for some extensions of the Lambek calculus”, Inform. and Comput., 287 (2022), 104760, 16 pp., arXiv: 2008.00070
|
8
[x]
|
| 91. |
Max I. Kanovich, Stepan G. Kuznetsov, Stepan L. Kuznetsov, Andre Scedrov, “Decidable fragments of calculi used in CatLog”, Natural Language Processing in Artificial Intelligence — NLPinAI 2021, Stud. Comput. Intell., 999, Springer, Cham, 2022, 1–24
|
1
[x]
|
| 92. |
Stepan L. Kuznetsov, “Reasoning in commutative Kleene algebras from *-free hypotheses”, Logica Yearbook 2021, College Publications, London, 2022, 99–113 |
| 93. |
Eben Blaisdell, Max Kanovich, Stepan L. Kuznetsov, Elaine Pimentel, Andre Scedrov, “Non-associative, non-commutative multi-modal linear logic”, Automated Reasoning, 11th International Conference, IJCAR 2022 (Haifa, Israel, August 8–10, 2022), Lecture Notes in Comput. Sci., 13385, Springer, Cham, 2022, 449–467
|
4
[x]
|
|
2021 |
| 94. |
Dhruv Mubayi, Alexander Razborov, “Polynomial to exponential transition in Ramsey theory”, Proc. London Math. Soc., 122:1 (2021), 69-92
|
10
[x]
|
| 95. |
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 |
| 96. |
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 |
| 97. |
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.
|
1
[x]
|
| 98. |
L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021, 31 pp., arXiv: 2108.06599 |
| 99. |
A. A. Razborov, “Pervoprokhodtsy teoreticheskoi informatiki”, Troitskii variant, Mart 2021, 1-3 https://trv-science.ru/2021/03/pervoproxodcy-teoreticheskoj-informatiki/ |
| 100. |
Igor Lysenok, Alexander Ushakov, “Orientable quadratic equations in free metabelian groups”, J. Algebra, 581 (2021), 303–326
|
7
[x]
|
| 101. |
L. Babai, K. A. Hansen, V. V. Podolskii, Xiaoming Sun, “Weights of exact threshold functions”, Izv. Math., 85:6 (2021), 1039–1059 |
| 102. |
M. N. Vyalyi, V. V. Podolskii, A. A. Rubtsov, D. A. Shvarts, A. Shen, Lektsii po diskretnoi matematike, Izdatelskii dom Vysshei Shkoly Ekonomiki, 2021, 496 pp. https://id.hse.ru/books/429927775.html
|
1
[x]
|
| 103. |
Fedor Pakhomov, James Walsh, “Reflection ranks and ordinal analysis”, J. Symb. Log., 86:4 (2021), 1350–1384, arXiv: 1805.02095
|
10
[x]
|
| 104. |
Fedor Pakhomov and James Walsh, Reflection ranks via infinitary derivations, 2021, 11 pp., arXiv: 2107.03521 |
| 105. |
Yury Savateev, Daniyar Shamkanov, “Non-well-founded proofs for the Grzegorczyk modal logic”, Rev. Symb. Log., 14:1 (2021), 22–50
|
11
[x]
|
| 106. |
Stanislav O. Speranski, “Negation as a modality in a quantified setting”, Journal of Logic and Computation, 31:5 (2021), 1330–1355
|
6
[x]
|
|
2022 |
| 107. |
S. O. Speranski, “Modal bilattice logic and its extensions”, Algebra and Logic, 60:6 (2022), 407–424 |
|
2021 |
| 108. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “The multiplicative-additive Lambek calculus with subexponential and bracket modalities”, J. Logic Lang. Inf., 30:1 (2021), 31–88
|
6
[x]
|
| 109. |
Stepan Kuznetsov, “Action logic is undecidable”, ACM Trans. Comput. Log., 22:2 (2021), 10, 26 pp., arXiv: 1912.11273
|
13
[x]
|
| 110. |
Stepan L. Kuznetsov, “Complexity of a fragment of infinitary action logic with exponential via non-well-founded proofs”, Automated Reasoning with Analytic Tableaux and Related Methods, 30th International Conference, TABLEAUX 2021, Birmingham, UK, September 6–9, 2021, Lecture Notes in Comput. Sci., 12842, Springer, Cham, 2021, 317–334
|
3
[x]
|
| 111. |
Stepan L. Kuznetsov, “Relational models for the Lambek calculus with intersection and unit”, Relational and Algebraic Methods in Computer Science. RAMiCS 2021, Marseille, November 2–5, 2021, Lecture Notes in Comput. Sci., 13027, Springer, Cham, 2021, 258–274
|
1
[x]
|
| 112. |
S. L. Kuznetsov, “Kleene star, subexponentials without contraction, and infinite computations”, Sib. elektron. matem. izv., 18:2 (2021), 905–922
|
2
[x]
|
| 113. |
S. M. Dudakov, B. N. Karlov, S. L. Kuznetsov, E. M. Fofanova, “Complexity of Lambek calculi with modalities and of total derivability in grammars”, Algebra and Logic, 60:5 (2021), 308–326 |
| 114. |
S. L. Kuznetsov, “Printsip dekompozitsii i algoritmicheskaya nerazreshimost dlya monoidov Klini s deleniyami”, Vserossiiskaya nauchnaya konferentsiya “Matematicheskie osnovy informatiki i informatsionno-kommunikatsionnykh sistem”. Sbornik trudov (Tver, 3–8 dekabrya 2021 g.), eds. S. M. Dudakov, B. N. Karlov, TvGU, Tver, 2021, 176–180 |
| 115. |
Stepan Kuznetsov, “Complexity of the infinitary Lambek calculus with Kleene star”, Rev. Symb. Log., 14:4 (2021), 946–972
|
6
[x]
|
|
2020 |
| 116. |
L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020, 84 pp., arXiv: 2012.11773 |
| 117. |
A. Razborov, Kvant, 2020, no. 10, 7–16 |
| 118. |
L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723 |
| 119. |
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 ;
|
2
[x]
|
| 120. |
S. I. Adian, V. M. Buchstaber, E. I. Zelmanov, S. V. Kislyakov, V. V. Kozlov, Yu. V. Matiyasevich, S. P. Novikov, D. O. Orlov, A. N. Parshin, V. L. Popov, D. V. Treschev, “Vladimir Petrovich Platonov (on his 80th birthday)”, Russian Math. Surveys, 75:2 (2020), 387–391 |
| 121. |
S. I. Adian, V. S. Atabekyan, “Normal Automorphisms of Free Groups of Infinitely Based Varieties”, Math. Notes, 108:2 (2020), 149–154 |
| 122. |
Alexander Kolpakov, Alexey Talambutsa, “Spherical and geodesic growth rates of right-angled Coxeter and Artin groups are Perron numbers”, Discrete Math., 343:3 (2020), 111763, 8 pp., arXiv: 1809.09591
|
2
[x]
|
| 123. |
A. Talambutsa, “On subquadratic derivational complexity of semi-Thue systems”, CSR 2020: Computer Science – Theory and Applications, 15th International Computer Science Symposium in Russia, Yekaterinburg, Russian Federation, 29 June 2020 - 3 July 2020, Lecture Notes in Comput. Sci., 12159, Springer, 2020, 379–392
|
1
[x]
|
| 124. |
Fedor V. Fomin, Vladimir V. Podolskii, “CSR 2018 Special Issue on TOCS”, Theory Comput. Syst., 64 (2020), 1–2 |
| 125. |
Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir Podolskii, Michael Zakharyaschev, “A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom”, Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, IJCAI Organization, 2020, 403–413
|
3
[x]
|
| 126. |
Alexander Kozachinskiy, Vladimir Podolski, “Multiparty Karchmer – Wigderson Games and Threshold Circuits”, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany, Leibniz Internat. Proc. in Inform., 169, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, 24, 23 pp. |
| 127. |
Anastasiya Chistopolskaya, Vladimir V. Podolskii, “On the Decision Tree Complexity of Threshold Functions”, Computer Science - Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 - July 3, 2020, Lecture Notes in Comput. Sci., 12159, Springer, Cham, 2020, 198–210 |
| 128. |
Dima Grigoriev, Vladimir V. Podolskii, “Tropical Combinatorial Nullstellensatz and sparse polynomials”, Found. Comput. Math., 20 (2020), 753–781
|
7
[x]
|
| 129. |
Vladimir V. Podolskii, Alexander A. Sherstov, “Inner Product and Set Disjointness: Beyond Logarithmically Many Parties”, ACM Trans. Comput. Theory, 12:4 (2020), 26, 28 pp.
|
1
[x]
|
| 130. |
A. Freund, F. Pakhomov, “Short proofs for slow consistency”, Notre Dame J. Formal Logic, 61:1 (2020), 31–49, arXiv: 1712.03251
|
2
[x]
|
| 131. |
Fedor Pakhomov, Alexander Zapryagaev, “Multi-dimensional Interpretations of Presburger Arithmetic in Itself”, J. Logic Comput., 30:8 (2020), 1681–1693, arXiv: 2004.03404
|
4
[x]
|
| 132. |
Daniyar Shamkanov, “Global neighbourhood completeness of the provability logic GLP”, Advances in Modal Logic (Helsinki, Finland, August 24–28, 2020), Advances in Modal Logic, 13, eds. Nicola Olivetti, Rineke Verbrugge, Sara Negri and Gabriel Sandu, College Publications, London, 2020, 581–596 |
| 133. |
Daniyar Shamkanov, “Non-well-founded derivations in the Gödel-Löb provability logic”, Rev. Symb. Log., 13:4 (2020), 776–796
|
2
[x]
|
| 134. |
Sergei P. Odintsov, Stanislav O. Speranski, “Belnap–Dunn modal logics: truth constants vs. truth values”, Review of Symbolic Logic, 13:2 (2020), 416–435
|
12
[x]
|
| 135. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “Reconciling Lambek's restriction, cut-elimination, and substitution in the presence of exponential modalities”, J. Logic Comput., 30:1 (2020), 239–256
|
6
[x]
|
| 136. |
S. L. Kuznetsov, N. S. Ryzhkova, “A restricted fragment of the Lambek calculus with iteration and intersection operations”, Algebra and Logic, 59:2 (2020), 129–146 |
| 137. |
Max Kanovich, Stepan Kuznetsov, Vivek Nigam, Andre Scedrov, “Soft subexponentials and multiplexing”, Automated Reasoning, 10th International Conference, IJCAR 2020, Paris, France, July 1–4, 2020, Lecture Notes in Comput. Sci., 12166, Springer, 2020, 500–517
|
5
[x]
|
| 138. |
Stepan Kuznetsov, “The ‘long rule’ in the Lambek calculus with iteration: undecidability without meets and joins”, AiML 2020, Helsinki, Finland, August 24–28, 2020, Advances in Modal Logic, 13, College Publications, London, 2020, 425–440
|
1
[x]
|
| 139. |
Stepan L. Kuznetsov, “A $\Pi^0_1$-bounded fragment of infinitary action logic with exponential”, Logic, Language, and Security: Scedrov Festschrift, Lecture Notes in Comput. Sci., 12300, Springer, Cham, 2020, 3–16
|
1
[x]
|
| 140. |
Stepan Kuznetsov, “Complexity of commutative infinitary action logic”, Dynamic Logic. New Trends and Applications, Third International Workshop, DaLi 2020, Prague, Czech Republic, October 9–10, 2020, Lecture Notes in Comput. Sci., 12569, Springer, Cham, 2020, 155–169
|
2
[x]
|
| 141. |
S. Kuznetsov, Kvant, 2020, no. 10, 32–33 |
|