Steklov Mathematical Institute

Home page

Russian page

Math-Net.Ru | MMS | MathSciNet | Zentralblatt MATH | Web-mail

About the Institute

Administration

Academic Council

Dissertation Councils

Staff

Events

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 доктор физ.-матем. наук, академик, заведующий отделом office: 508; tel.: +7 (499) 135 15 69, +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 доктор физ.-матем. наук, член-корр. РАН, главный научный сотрудник 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. Recent publications
Lysenok Igor Geront'evich доктор физ.-матем. наук, ведущий научный сотрудник 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. Recent publications
Podolskii Vladimir Vladimirovich кандидат физ.-матем. наук, научный сотрудник 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. Recent publications
Razborov Aleksandr Aleksandrovich доктор физ.-матем. наук, член-корр. РАН, главный научный сотрудник 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. Recent publications
Shamkanov Daniyar Salkarbekovich кандидат физ.-матем. наук, научный сотрудник office: 515; tel.: +7 (495) 984 81 43; e-mail: daniyar@mi.ras.ru Principal fields of research: Proof theory. Nonclassical logics. Combinatory logic. Recent publications
Talambutsa Alexey Leonidovich кандидат физ.-матем. наук, научный сотрудник 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. Recent publications

Makanin Gennadii Semenovich доктор физ.-матем. наук, внештатный сотрудник e-mail: makanin@mi.ras.ru Principal fields of research: Combinatorial group theory. Algorithmic problems of semigropus theory. Recent publications

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

by years

scientific publications

by types


2013
1.	H. Hatami, J. Hladky, D. Kral, S. Norin, A. A. Razborov, “On the number of pentagons in triangle-free graphs”, Journal of Combinatorial Theory, series A, 120:3 (2013), 722–732
2.	A. Razborov, “On the Caccetta-Haggkvist conjecture with forbidden subgraphs”, Journal of Graph Theory, 2013 (to appear) , arXiv: 1107.2247
3.	A. A. Razborov, “O (3,4)-probleme Turana s zapreschënnymi podgrafami”, Matem. zametki, 2013 (to appear) , arXiv: 1210.4605
4.	L. Beklemishev, D. Gabelaia, “Topological completeness of provability logic GLP”, Annals of Pure and Applied Logic, 2013 (to appear)

2012
5.	O. Pikhurko, A. Razborov, Asymptotic Structure of Graphs with the Minimum Number of Triangles, 2012, arXiv: 1204.2846
6.	O. Beyersdorff, N. Galesi, M. Lauria, A. A. Razborov, “Parameterized Bounded-Depth Frege is Not Optimal”, ACM Transactions on Computation Theory, 4 (2012), 7, 16 pp.
7.	H. Hatami, J. Hladky, D. Kral, S. Norin, A. A. Razborov, “Non-Three-Colorable Common Graphs Exist”, Combinatorics, Probability and Computing, 21:5 (2012), 734-742
8.	L. D. Beklemishev, “Calibrating provability logic: from modal logic to reflection calculus”, Advances in Modal Logic, 9, eds. T. Bolander, T. Braüner, S. Ghilardi, L. Moss, College Publications, London, 2012, 89–94
9.	L. Beklemishev, D. Gabelaia, Topological interpretations of provability logic, 2012, 37 pp., arXiv: 1210.7317
10.	L. Beklemishev, D. Fernández-Duque, J. Joosten, On provability logics with linearly ordered modalities, 2012, 36 pp., arXiv: 1210.4809
11.	L. Beklemishev, Yu. Gurevich, “Propositional primal logic with disjunction”, Journal of Logic and Computation, 2012, 26 pp. (published online)
12.	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
13.	V. V. Podolskii, “Exponential lower bound for bounded depth circuits with few threshold gates”, Inform. Process. Lett., 112:7 (2012), 267–271
14.	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
15.	K. A. Hansen, R. Ibsen-Jensen, V. V. Podolskii, E. P. Tsigaridas, Patience of matrix games, 2012, 32 pp., arXiv: 1206.1751
16.	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
17.	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

2011
18.	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
19.	Alexander A. Razborov, “On the Fon-Der-Flaass interpretation of extremal examples for Turán's $(3,4)$-problem”, Proc. Steklov Inst. Math., 274 (2011), 247–266
20.	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
21.	G. S. Makanin, “Parametrization of the Solutions of the Equation $x_1x_2…x_{n-1}x_n=x_nx_{n-1}…x_2x_1$ in a Free Monoid”, Math. Notes, 89:6 (2011), 839–844
22.	L. Beklemishev, D. Gabelaia, Topological completeness of the provability logic GLP, 2011, 26 pp., arXiv: 1106.5693v1
23.	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
24.	L. D. Beklemishev, “A simplified proof of arithmetical completeness theorem for provability logic GLP”, Proc. Steklov Inst. Math., 274:1 (2011), 25–33
25.	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.
26.	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
27.	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.
28.	L. D. Beklemishev, “Foreword”, Proc. Steklov Inst. Math., 274 (2011), 1–3
29.	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
30.	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
31.	Vladimir V. Podolskii, “Degree-uniform lower bound on the weights of polynomials with given sign function”, Proc. Steklov Inst. Math., 274 (2011), 231–246
32.	Daniyar S. Shamkanov, “Interpolation properties for provability logics $\mathbf{GL}$ and $\mathbf{GLP}$”, Proc. Steklov Inst. Math., 274 (2011), 303–316
33.	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

2010
34.	A. A. Razborov, “On 3-hypergraphs with forbidden 4-vertex configurations”, SIAM J. Discrete Math., 24:3 (2010), 946–963
35.	V. Guruswami, J. R. Lee, A. Razborov, “Almost Euclidean subspaces of $\ell^N_1$ via expander codes”, Combinatorica, 30:1 (2010), 47–68
36.	S. Artemov, V. Diekert, A. Razborov, “Preface”, Symposium on Computer Science (Moscow, June 7–12, 2008), Theory Comput. Syst., 46, no. 4, 2010, 619
37.	A. A. Razborov, A. A. Sherstov, “The sign-rank of $\mathrm{AC}^0$”, SIAM J. Comput., 39:5 (2010), 1833–1855
38.	F. Eisenbrand, N. Hähnle, A. Razborov, T. Rothvoß, “Diameter of polyhedra: limits of abstraction”, Math. Oper. Res., 35:4 (2010), 786–794
39.	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
40.	O. Kharlampovich, I. G. Lysë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
41.	L. D. Beklemishev, “Gödel incompleteness theorems and the limits of their applicability. I”, Russian Math. Surveys, 65:5 (2010), 857–899
42.	L. D. Beklemishev, “Kripke semantics for provability logic GLP”, Ann. Pure Appl. Logic, 161:6 (2010), 756–774
43.	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.
44.	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
45.	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
46.	A. L. Talambutsa, “Attainability of the Minimal Exponent of Exponential Growth for Some Fuchsian Groups”, Math. Notes, 88:1 (2010), 144–148
47.	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
48.	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
49.	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

2009
50.	A. A. Razborov, “A simple proof of Bazzi's theorem”, ACM Transactions on Computation Theory (TOCT), 1:1 (2009), 3, 5 pp.
51.	V. V. Podolskii, “Perceptrons of large weight”, Problems Inform. Transmission, 45:1 (2009), 46–53
52.	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

2008
53.	M. Alekhnovich, A. A. Razborov, “Resolution is not automatizable unless $W[P]$ is tractable”, SIAM J. Comput., 38:4 (2008), 1347–1363
54.	A. A. Razborov, “On the minimal density of triangles in graphs”, Combin. Probab. Comput., 17:4 (2008), 603–618
55.	O. Kharlampovich, I. G. Lysenok, A. G. Myasnikov, N. W. M. Touikan, Quadratic equations over free groups are NP-complete, 2008, arXiv: 0802.3839
56.	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