Home page
Home page
Home page
Russian page
English page
Math-Net.Ru | MMS | MathSciNet | Zentralblatt MATH | Web-mail 

   
 About the Institute
 Administration
 Academic Council
 Dissertation Councils
 Departments
Staff 
 Publications
 Seminars
 Conferences
 Events
 Publications
 In memoriam
 Photogallery
 Library


    Address
Gubkina str. 8,
119991, Moscow, Russia
Tel.: +7(495) 984 81 41
Fax: +7(495) 984 81 39
Web site: www.mi.ras.ru
E-mail: steklov@mi.ras.ru

View Map
Transit directions

   

Department of Mathematical Logic

| Seminars | Publications |
Staff
Adian Sergei Ivanovich

Doctor Phys.-Math. Sci., Academician, Head of Department
office: 508; tel.: +7 (499) 941 01 83, +7 (495) 984 81 41 * 36 34; e-mail: sia@mi.ras.ru
Principal fields of research: Algorithmic problems in algebras. Semigroups theory. Groups theory.
Beklemishev Lev Dmitrievich

Doctor Phys.-Math. Sci., Corresponding Member of RAS, Chief Scientific Researcher
office: 515; tel.: +7 (495) 984 81 43, +7 (495) 984 81 41 * 37 44; e-mail: bekl@mi.ras.ru
Principal fields of research: Mathematical logic. Proof theory. Provability logic. Modal logic. Fragments of arithmetic.
Kuznetsov Stepan L'vovich

Candidate Phys.-Math. Sci., Scientific Researcher
office: 515; tel.: +7 (495) 984 81 41 * 37 44; e-mail: skuzn@inbox.ru
Lysenok Igor Geront'evich

Doctor Phys.-Math. Sci., Leading Scientific Researcher
office: 507; tel.: +7 (495) 984 81 41 * 37 52; e-mail: lysionok@mi.ras.ru
Principal fields of research: Combinatorial group theory. Algorithmic problems of group theory.
Podolskii Vladimir Vladimirovich

Candidate Phys.-Math. Sci., Senior Scientific Researcher
office: 506; tel.: +7 (495) 984 81 41 * 36 33; e-mail: podolskii@mi.ras.ru
Personal page: http://www.mi.ras.ru/~podolskii/
Principal fields of research: Computational complexity theory.
Razborov Aleksandr Aleksandrovich

Doctor Phys.-Math. Sci., Corresponding Member of RAS, Chief Scientific Researcher
office: 506; tel.: +7 (495) 984 81 41 * 37 46; e-mail: razborov@mi.ras.ru
Personal page: http://www.mi.ras.ru/~razborov/
Principal fields of research: Complexity of proofs and computations.
Shamkanov Daniyar Salkarbekovich

Candidate Phys.-Math. Sci., Scientific Researcher
office: 515; tel.: +7 (495) 984 81 43; e-mail: daniyar@mi.ras.ru
Principal fields of research: Proof theory. Nonclassical logics. Combinatory logic.
Talambutsa Alexey Leonidovich

Candidate Phys.-Math. Sci., Scientific Researcher
office: 515; tel.: +7 (495) 984 81 41 * 37 44; e-mail: altal@mi.ras.ru
Principal fields of research: Combinatorial group theory. Algorithmic problems for groups and semigroups.

Makanin Gennadii Semenovich

Doctor Phys.-Math. Sci., Out-Of-Staff Member
e-mail: makanin@mi.ras.ru
Principal fields of research: Combinatorial group theory. Algorithmic problems of semigropus theory.
Top
Seminars
Algorithmic problems in algebra and logic
Seminar Chairman: S. I. Adian
MSU, auditorium 16-04
Special seminar "Geometric Theory of Groups"
Seminar Chairman: I. G. Lysenok
Steklov Mathematical Institute, Room 430 (8 Gubkina)
Recent publications

Steklov Mathematical Institute staff Steklov Mathematical Institute staff and out-of-staff employees
| by years | scientific publications | by types |


   2015
1. A. Razborov, “Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution”, Ann. of Math. (2), 2015 (to appear) , http://annals.math.princeton.edu/articles/9004

   2014
2. A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254  mathnet  crossref  crossref  isi  elib
3. A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429  crossref  mathscinet  zmath  isi
4. S. I. Adian, V. S. Atabekyan, “The Hopfian Property of $n$-Periodic Products of Groups”, Math. Notes, 95:4 (2014), 443–449  mathnet  crossref  crossref  isi
5. L. D. Beklemishev, D. Fernández-Duque, J. J. Joosten, “On provability logics with linearly ordered modalities”, Studia Logica, 102:3 (2014), 541–566  crossref  mathscinet (cited: 1)  isi (cited: 1)
6. L. Beklemishev, “Positive provability logic for uniform reflection principles”, Ann. Pure Appl. Logic, 165:1 (2014), 82–105  crossref  mathscinet (cited: 1)  zmath  isi
7. L. Beklemishev, Y. Gurevich, “Propositional primal logic with disjunction”, J. Logic Comput., 24:1 (2014), 257–282  crossref  mathscinet  zmath  isi
8. L. Beklemishev, D. Gabelaia, “Topological interpretations of provability logic”, Leo Esakia on duality in modal and intuitionistic logics, Outstanding Contributions to Logic, 4, eds. G. Bezhanishvili, Springer, 2014, 257–290  crossref
9. Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii, “Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries”, Description Logics 2014, CEUR Workshop Proceedings, 2014, 45–57, http://ceur-ws.org/Vol-1193/paper_43.pdf
10. G. Gottlob, S, Kikot, R. Kontchakov, V. V. Podolskii, Th. Schwentick, M. Zakharyaschev, “The price of query rewriting in ontology-based data access”, Artificial Intelligence, 213 (2014), 42–59  crossref  mathscinet  zmath  isi
11. S. Kikot, R. Kontchakov, V. Podolskii, M. Zakharyaschev, “On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Bounded Chase”, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), ACM Digital Library, 2014, 10, arXiv: 1401.4420
12. S. Kuznetsov, “$L$-completeness of the Lambek calculus with the reversal operation allowing empty antecedents”, Categories and types in logic, language, and physics. Essays dedicated to Jim Lambek on the occasion of his 90th birthday, Lecture Notes in Computer Science, 8222, eds. C. Casadio, B. Coecke, M. Moortgat, P. Scott, Springer, Berlin, Heidelberg, 2014, 268–278  crossref  zmath
13. S. L. Kuznetsov, “Trivalent logics arising from L-models for the Lambek calculus with constants”, Journal of Applied Non-Classical Logics, 14:1-2 (2014), 132–137  crossref  mathscinet

   2013
14. 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  crossref  mathscinet (cited: 10)  zmath  isi (cited: 3)  elib (cited: 1)
15. A. Razborov, “On the Caccetta-Häggkvist conjecture with forbidden subgraphs”, J. Graph Theory, 74:2 (2013), 236–248, arXiv: 1107.2247  crossref  mathscinet  zmath  isi
16. E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17, 8 pp.  crossref  mathscinet
17. A. A. Razborov, “What is a Flag Algebra?”, Notices Amer. Math. Soc., 60:10 (2013), 1324–1327  crossref  mathscinet
18. A. Razborov, “Flag Algebras: an Interim Report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232
19. A. A. Agrachëv, D. V. Anosov, S. M. Aseev, V. M. Buchstaber, A. M. Vershik, Ya. B. Vorobets, V. A. Kaimanovich, B. S. Kashin, I. G. Lysënok, A. Yu. Ol'shanskii, V. N. Remeslennikov, Ya. G. Sinai, S. K. Smirnov, A. M. Stepin, I. A. Taimanov, E. V. Shchepin, “Rostislav Ivanovich Grigorchuk (on his sixtieth birthday)”, Russian Math. Surveys, 68:5 (2013), 967–971  mathnet  crossref  crossref  mathscinet  adsnasa  isi
20. I. Lysenok, A. Ushakov, Spherical quadratic equations in free metabelian groups, 2013, 9 pp., arXiv: 1304.4898
21. I. Lysenok, A. Miasnikov, A. Ushakov, Quadratic equations in the Grigorchuk group, 2013, 23 pp., arXiv: 1304.5579
22. L. Beklemishev, D. Gabelaia, “Topological completeness of the provability logic GLP”, Ann. Pure Appl. Logic, 164:12 (2013), 1201–1223  crossref  mathscinet (cited: 5)  isi (cited: 3)  elib (cited: 1)  scopus
23. L. D. Beklemishev, “Pozitivnye logiki dokazuemosti”, Mezhdunarodnaya konferentsiya “Maltsevskie chteniya”. Tezisy dokladov (Novosibirsk, 11–15 noyabrya 2013 g.), FGBUN Institut matematiki im. S.L. Soboleva SO RAN; Novosibirskii gosudarstvennyi universitet, Novosibirsk, 2013, 10, www.math.nsc.ru/conference/malmeet/13/maltsev13.pdf
24. V. V. Podolskii, “Lower bound on weights of large degree threshold functions”, Log. Methods Comput. Sci., 9:2 (2013), 13, 17 pp.  crossref  mathscinet  zmath  isi  elib  scopus
25. K. A. Hansen, V. V. Podolskii, “Polynomial threshold functions and Boolean threshold circuits”, Mathematical Foundations of Computer Science 2013, 38th International Symposium, MFCS 2013 (Klosterneuburg, Austria, August 26–30, 2013), Proceedings, Lecture Notes in Computer Science, 8087, Springer, Berlin–Heidelberg, 2013, 516–527  crossref  zmath  scopus
26. K. A. Hansen, V. V. Podolskii, Polynomial threshold functions and Boolean threshold circuits, http://eccc.hpi-web.de/report/2013/021/, Electronic Colloquium on Computational Complexity (ECCC), 2013, 25 pp.
27. S. Kikot, R. Kontchakov, V. V. Podolskii, M. Zakharyaschev, “Query Rewriting over Shallow Ontologies”, Description Logics 2013, Informal Proceedings of the 26th International Workshop on Description Logics (Ulm, Germany, July 23–26, 2013), CEUR Workshop Proceedings, 1014, CEUR Workshop Proceedings, 2013, 316–327, http://ceur-ws.org/Vol-1014/paper_27.pdf
28. K. A. Hansen, R. I. Jensen, V. V. Podolskii, E. P. Tsigaridas, “Patience of matrix games”, Discrete Appl. Math., 161:16–17 (2013), 2440–2459  crossref  mathscinet  zmath  isi  elib  scopus
29. S. Kuznetsov, “Conjunctive grammars in Greibach normal form and the Lambek calculus with additive connectives”, Formal grammar. 17th and 18th international conferences, FG 2012, Opole, Poland, August 2012, revised selected papers, FG 2013, Düsseldorf, Germany, August 2013, Proceedings, Lecture Notes in Computer Science, 8036, Springer, Berlin, 2013, 242–249, ISBN: 978-3-642-39997-8/pbk  crossref  zmath  elib

   2012
30. O. Pikhurko, A. Razborov, Asymptotic Structure of Graphs with the Minimum Number of Triangles, 2012, arXiv: 1204.2846
31. 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.  crossref
32. 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  mathscinet (cited: 6)  zmath  isi (cited: 2)  elib (cited: 2)
33. A. A. Razborov, Kommunikatsionnaya slozhnost, MTsNMO, 2012, s saita MTsNMO
34. S. I. Adian, “On a method for proving exact bounds on derivational complexity in Thue systems”, Math. Notes, 92:1 (2012), 3–15  mathnet  crossref  crossref  zmath  isi  elib  elib  scopus
35. L. D. Beklemishev, “Calibrating provability logic: from modal logic to reflection calculus”, Advances in Modal Logic, 9, eds. T. Bolander, T. Braüner, S. Ghilardi, L. Moss, College Publications, London, 2012, 89–94  zmath
36. L. Beklemishev, D. Gabelaia, Topological interpretations of provability logic, 2012, 37 pp., arXiv: 1210.7317
37. L. Beklemishev, D. Fernández-Duque, J. Joosten, On provability logics with linearly ordered modalities, 2012, 36 pp., arXiv: 1210.4809
38. L. Beklemishev, G. Bezhanishvili, D. Mundici, Y. Venema, “Foreword [Special issue dedicated to the memory of Leo Esakia]”, Studia Logica, 100:1-2 (2012), 1–7  crossref  mathscinet  isi  scopus
39. L. Beklemishev, “DKAL: A Distributed Knowledge Authorization Language and Its Logic of Information”, Computer Science – Theory and Applications. 7th International Computer Science Symposium in Russia, CSR 2012 (Nizhny Novgorod, Russia, July 3–7, 2012), Lecture Notes in Computer Science, 7353, eds. E. Hirsch, J. Karhumäki, A. Lepistö, M. Prilutskii, Springer, 2012, XIII–XIV  crossref
40. M. Bucher, A. Talambutsa, Exponential growth rates of free and amalgamated products, Report No. 36, 2011/2012, spring, Institut Mittag-Leffler, Swedish Royal Academy of Science, Djursholm, 2012, 17 pp., IML-1112s-36.pdf
41. V. V. Podolskii, “Exponential lower bound for bounded depth circuits with few threshold gates”, Inform. Process. Lett., 112:7 (2012), 267–271  crossref  mathscinet  zmath  isi  elib  scopus
42. V. V. Podolskii, “Lower bound on weights of large degree threshold functions”, How the World Computes, Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 (Cambridge, UK, June 18–23, 2012), Proceedings, Lecture Notes in Comput. Sci., 7318, Springer–Berlin–Heidelberg, 2012, 599–608, arXiv: 1204.2652  crossref  mathscinet  zmath  scopus
43. K. A. Hansen, R. Ibsen-Jensen, V. V. Podolskii, E. P. Tsigaridas, Patience of matrix games, 2012, 32 pp., arXiv: 1206.1751
44. D. Grigoriev, V. V. Podolskii, Complexity of tropical and min-plus linear prevarieties, The MPIM preprint series, 2012-23, Bonn, 2012, 36 pp., http://www.mpim-bonn.mpg.de/preblob/5202, arXiv: 1204.4578
45. S. Kikot, R. Kontchakov, V. V. Podolskii, M. Zakharyaschev, “Exponential lower bounds and separation for query rewriting”, Automata, Languages, and Programming, 39th International Colloquium, ICALP 2012 (Warwick, UK, July 9–13, 2012), Proceedings, Part II, Lecture Notes in Comput. Sci., 7392, Springer Berlin Heidelberg, 2012, 263–274, arXiv: 1202.4193  crossref  mathscinet  zmath  elib (cited: 1)
46. S. Kuznetsov, “L-completeness of the Lambek calculus with the reversal operation”, Logical aspects of computational linguistics, Lecture Notes in Comput. Sci., 7351, Springer, Heidelberg, 2012, 151–160  crossref  mathscinet (cited: 1)
47. S. Kuznetsov, “Lambek grammars with the unit”, Formal grammar. 15th and 16th international conferences, FG 2010, Copenhagen, Denmark, August 2010, FG 2011, Ljubljana, Slovenia, August 2011. Revised selected papers, Lecture Notes in Comput. Sci., 7395, Springer, Berlin, 2012, 262–266, ISBN: 978-3-642-32023-1/pbk  crossref  zmath
48. S. Kuznetsov, “Lambek grammars with one division and one primitive type”, Log. J. IGPL, 20:1 (2012), 207–221  crossref  mathscinet  zmath  isi
49. S. L. Kuznetsov, Kategorialnye grammatiki, osnovannye na variantakh ischisleniya Lambeka, Diss. … kand. fiz.-matem. nauk, MGU imeni M. V. Lomonosova, M., 2012, 70 pp., polnyi tekst (PDF), avtoreferat (PDF)

   2011
50. 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 (cited: 1)  zmath
51. L. D. Beklemishev, V. M. Buchstaber, I. G. Lysenok, A. A. Mal'tsev, S. P. Novikov, A. A. Razborov, A. L. Semenov, “Sergei Ivanovich Adian (on his eightieth birthday)”, Russian Math. Surveys, 66:1 (2011), 197–198  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
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  mathnet  crossref  mathscinet  isi (cited: 4)  elib
53. 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 (cited: 1)  zmath
54. M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678  crossref  mathscinet (cited: 1)  zmath  isi  elib (cited: 1)  scopus
55. 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
56. Igor G. Lysenok, Alexei G. Myasnikov, “A polynomial bound on solutions of quadratic equations in free groups”, Proc. Steklov Inst. Math., 274 (2011), 136–173  mathnet  crossref  mathscinet  isi  elib
57. S. Adian, L. Beklemishev, A. Visser, “Proof and Computation”, J. Logic Computation, 21:4 (2011), 541–542  crossref  isi
58. P. S. Novikov, S. I. Adian, “On a semicontinuous function”, Proc. Steklov Inst. Math., 274 (2011), 4–8  mathnet  crossref  mathscinet  isi  elib
59. L. Beklemishev, D. Gabelaia, Topological completeness of the provability logic GLP, 2011, 26 pp., arXiv: 1106.5693
60. L. Beklemishev, Y. Gurevich, Propositional primal logic with disjunction, Microsoft Research Technical Report MSR-TR-2011-35, Redmond, 2011, 31 pp., http://research.microsoft.com/apps/pubs/default.aspx?id=146631
61. L. D. Beklemishev, “A simplified proof of arithmetical completeness theorem for provability logic GLP”, Proc. Steklov Inst. Math., 274:1 (2011), 25–33  mathnet  crossref  mathscinet  isi (cited: 3)  elib
62. L. Beklemishev, R. de Queiroz (eds.), Logic, language, information, and computation, 18th International Workshop, WoLLIC 2011 (Philadelphia, PA, USA, May 18–20, 2011), Proceedings, Lecture Notes in Comput. Sci., 6642, Springer, 2011, x+311 pp.  crossref  zmath
63. L. Beklemishev, “Ordinal completeness of bimodal provability logic GLB”, Logic, language, and computation, 8th International Tbilisi Symposium TbiLLC 2009, Lecture Notes in Comput. Sci., 6618, eds. N. Bezhanishvili et al., Springer, Heidelberg, 2011, 1–15  crossref  mathscinet (cited: 2)  zmath  isi (cited: 2)  scopus
64. Algoritmicheskie voprosy algebry i logiki, Sbornik statei. K 80-letiyu so dnya rozhdeniya akademika Sergeya Ivanovicha Adyana, Tr. MIAN, 274, ed. L. D. Beklemishev, E. F. Mischenko, MAIK, M., 2011, 351 pp.  mathnet
65. L. D. Beklemishev, “Foreword”, Proc. Steklov Inst. Math., 274 (2011), 1–3  mathnet  crossref  mathscinet  scopus
66. A. L. Talambutsa, “On the attainability of the minimal growth exponent of free products of cyclic groups”, Russian Math. Surveys, 66:1 (2011), 179–180  mathnet  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib  scopus
67. A. L. Talambutsa, “Attainability of the minimal exponential growth rate for free products of finite cyclic groups”, Proc. Steklov Inst. Math., 274 (2011), 289–302  mathnet  crossref  mathscinet  isi  elib
68. Vladimir V. Podolskii, “Degree-uniform lower bound on the weights of polynomials with given sign function”, Proc. Steklov Inst. Math., 274 (2011), 231–246  mathnet  crossref  mathscinet  isi (cited: 1)  elib
69. Daniyar S. Shamkanov, “Interpolation properties for provability logics $\mathbf{GL}$ and $\mathbf{GLP}$”, Proc. Steklov Inst. Math., 274 (2011), 303–316  mathnet  crossref  mathscinet  isi (cited: 1)  elib
70. D. S. Shamkanov, “Strong normalization and confluence for reflexive combinatory logic”, Logic, language, information and computation, 18th international workshop, WoLLIC 2011 (Philadelphia, PA, USA, May 18–20, 2011), Proceedings, Lecture Notes in Computer Science, 6642, eds. L. D. Beklemishev et al., Springer, Berlin, 2011, 228–238  crossref  zmath  isi
71. S. L. Kuznetsov, “On the Lambek calculus with a unit and one division”, Moscow University Math. Bull., 66:4 (2011), 173–175  crossref  mathscinet  elib  elib

   2010
72. A. A. Razborov, “On 3-hypergraphs with forbidden 4-vertex configurations”, SIAM J. Discrete Math., 24:3 (2010), 946–963  crossref  mathscinet (cited: 20)  zmath  isi (cited: 20)  elib (cited: 15)
73. 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 (cited: 1)  isi (cited: 2)  elib (cited: 3)  scopus
74. 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  isi
75. A. A. Razborov, A. A. Sherstov, “The sign-rank of $\mathrm{AC}^0$”, SIAM J. Comput., 39:5 (2010), 1833–1855  crossref  mathscinet (cited: 6)  zmath  isi (cited: 7)  elib (cited: 6)  scopus
76. 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 (cited: 4)  zmath  isi (cited: 7)
77. I. Lysenok, A. Myasnikov, A. Ushakov, “The conjugacy problem in the Grigorchuk group is polynomial time decidable”, Groups Geom. Dyn., 4:4 (2010), 813–833, arXiv: 0808.2502  crossref  mathscinet (cited: 3)  zmath  adsnasa  isi (cited: 2)  elib (cited: 2)  scopus
78. O. Kharlampovich, I. G. Lysënok, A. G. Myasnikov, N. W. M. Touikan, “The solvability problem for quadratic equations over free groups is NP-complete”, Theory Comput. Syst., 47:1 (2010), 250–258  crossref  mathscinet (cited: 2)  zmath  isi (cited: 3)  elib (cited: 2)  scopus
79. S. I. Adian, “Once More on Periodic Products of Groups and on a Problem of A. I. Maltsev”, Math. Notes, 88:6 (2010), 771–775  mathnet  crossref  crossref  mathscinet  isi (cited: 2)  elib  scopus
80. S. I. Adian, “The Burnside problem and related topics”, Russian Math. Surveys, 65:5 (2010), 805–855  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi (cited: 2)  elib (cited: 2)  elib (cited: 2)  scopus
81. L. D. Beklemishev, “Gödel incompleteness theorems and the limits of their applicability. I”, Russian Math. Surveys, 65:5 (2010), 857–899  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib  scopus
82. L. D. Beklemishev, “Kripke semantics for provability logic GLP”, Ann. Pure Appl. Logic, 161:6 (2010), 756–774  crossref  mathscinet (cited: 8)  zmath  isi (cited: 8)  elib (cited: 8)  scopus
83. L. Beklemishev, V. Goranko, V. Shehtman (eds.), Advances in Modal Logic, 8, College Publications, London, 2010, ISBN: 978-1-84890-013-4, ix+505 pp.  mathscinet (cited: 1)
84. L. Beklemishev, G. Bezhanishvili, T. Icard, “On topological models of GLP”, Ways of proof theory, Ontos Mathematical Logic, 2, eds. R. Schindler, Ontos Verlag, Frankfurt, 2010, 133–153  mathscinet (cited: 4)
85. L. Beklemishev, “On the Craig interpolation and the fixed point properties of GLP”, Proofs, categories and computations, Tributes, 13, eds. S. Feferman et al., College Publications, London, 2010, 49–60  mathscinet (cited: 2)  zmath
86. A. L. Talambutsa, “Attainability of the Minimal Exponent of Exponential Growth for Some Fuchsian Groups”, Math. Notes, 88:1 (2010), 144–148  mathnet  mathnet  crossref  crossref  mathscinet  zmath  isi (cited: 1)  elib  elib  scopus
87. V. V. Podolskii, A. A. Sherstov, “A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length”, Math. Notes, 87:6 (2010), 860–873  mathnet  crossref  crossref  mathscinet  isi (cited: 1)  elib (cited: 2)  elib (cited: 2)
88. K. A. Hansen, V. V. Podolskii, “Exact threshold circuits”, Proc. of 25th Annual IEEE Conference on Computational Complexity (CCC), IEEE Computer Soc., Los Alamitos, CA, 2010, 270–279  crossref  mathscinet  isi (cited: 1)  scopus
89. L. Babai, K. A. Hansen, V. Podolskii, Sun Xiaoming, “Weights of exact threshold functions”, Mathematical foundations of computer science 2010, Proc. of 35th International Symposium on Mathematical Foundations of Computer Science (MFCS) (Brno, Czech Republic, 2010), Lecture Notes in Comput. Sci., 6281, Springer, Berlin, 2010, 66–77  crossref  mathscinet (cited: 2)  zmath  isi (cited: 1)  scopus

   2009
90. A. A. Razborov, “A simple proof of Bazzi's theorem”, ACM Transactions on Computation Theory (TOCT), 1:1 (2009), 3, 5 pp.  crossref
91. S. I. Adian, “Upper bound on the derivational complexity in some word rewriting system”, Dokl. Math., 80:2 (2009), 679–683  mathnet  crossref  mathscinet  zmath  isi (cited: 1)  elib (cited: 1)  elib (cited: 1)  scopus
92. V. V. Podolskii, “Perceptrons of large weight”, Problems Inform. Transmission, 45:1 (2009), 46–53  mathnet  crossref  mathscinet  zmath  isi (cited: 5)  elib (cited: 7)
93. V. V. Podolskii, A. A. Sherstov, “Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length”, Russian Math. Surveys, 64:5 (2009), 950–951  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
94. S. L. Kuznetsov, “On the Lambek calculus with one division and one primitive type that allows empty antecedents”, Moscow University Math. Bull., 64:2 (2009), 76–79  crossref  mathscinet  elib (cited: 1)  elib (cited: 1)

   2008
95. M. Alekhnovich, A. A. Razborov, “Resolution is not automatizable unless $W[P]$ is tractable”, SIAM J. Comput., 38:4 (2008), 1347–1363  crossref  mathscinet (cited: 6)  zmath  isi (cited: 12)  elib (cited: 6)
96. A. A. Razborov, “On the minimal density of triangles in graphs”, Combin. Probab. Comput., 17:4 (2008), 603–618  crossref  mathscinet (cited: 27)  zmath  isi (cited: 28)  elib (cited: 21)
97. O. Kharlampovich, I. G. Lysenok, A. G. Myasnikov, N. W. M. Touikan, Quadratic equations over free groups are NP-complete, 2008, arXiv: 0802.3839  adsnasa
98. S. I. Adian, “Groups with Periodic Defining Relations”, Math. Notes, 83:3 (2008), 293–300  mathnet  crossref  crossref  mathscinet  zmath  isi (cited: 1)  elib (cited: 1)  elib (cited: 1)
99. V. V. Podolskii, “A uniform lower bound on weights of perceptrons”, Computer science—theory and applications, Lecture Notes in Comput. Sci., 5010, Springer, Berlin, 2008, 261–272  crossref  mathscinet (cited: 4)  zmath  isi (cited: 5)
Home page

© Steklov Mathematical Institute, 2004–2014