
Meeting #206
Alexander Rybalov
(Sobolev Institute of Mathematics, Omsk, Russia)"Generic complexity of the subset sum problem for some semigroups"
Abstract.The subset sum problem is a classical combinatorial problem, studied for many decades. This problem is very popular in cryptography, where there are many cryptosystems based on it. Myasnikov, Nikolaev and Ushakov in 2015 introduced analogs of the subset sum problem for arbitrary groups (semigroups). They explored the computational complexity of these problems for various groups: polynomial solvability is proved for hyperbolic groups, \(NP\)completeness is proved for BaumslagSolitar groups. In this talk I present results about generic polynomial decidability of the subset sum problem for following semigroups: monoid \(Mat(N,k)\) of \(k\) x \(k\) matrices with natural entries, monoid \(SL(N,2)\) of unimodular \(2\)x\(2\) matrices with natural entries, groups \(PSL(Z,2)\) and \(SL(Z,2)\), and some Brandt semigroups.

Meeting #205
Alexei Miasnikov
(Stevens Institute)"The Diophantine problem in classical matrix groups"
Abstract.The Diophantine problem in a group (ring) \(G\) is decidable if there exists an algorithm that given a finite system of equations with coefficients in \(G\) decides whether or not the system has a solution in \(G\). I will discuss the Diophantine problem in the groups the classical matrix groups \(G_n(R)\), where \(R\) is an associative unitary ring, \(n > 2\), and \(G(n,R)\) is one of the groups \(GL(n,R)\), \(SL(n,R)\), \(T(n,R)\), \(UT(n,R)\), \(PGL(n,R)\), or \(PSL(n,R)\) (in the last two cases we assume that \(R\) is also commutative). The main result is that the Diophantine problem in \(G(n,R)\) with a chosen set of coefficients is Ptime reducible (Karp reducible) to the Diophantine problem in R with respect to a suitable set of coefficients in \(R\). What is much more interesting is that the converse is also true. In the case when the ring \(R\) is finitely generated and commutative the result above allows one to clarify the situation completely, modulo a big conjecture in number theory. For not finitely generated rings, more so for uncountable rings, decidability of the Diophantine problem heavily depends on the set of constants. The case of classical fields of reals, complex and padic numbers is especially interesting, as well as the rings of padic integers (which is related to pro p completions of groups). I am going to touch on this subject and, if time permits, show some surprising examples. The talk is based on joint results with Mahmood Sohrabi.

Meeting #204
Markus Lohrey
(Siegen University, Germany)"Knapsack and the power word problem in solvable BaumslagSolitar groups"
Abstract.We show that the power word problem for a solvable BaumslagSolitar groups \(BS(1,q)\) belongs to the circuit complexity class \(TC0\); a very small complexity class within polynomial time (even logspace). The power word problem is a succinct version of the classical word problem, where the input consists of group elements \(g_1,…, g_d\) (encoded as words over a set of generators) and binary encoded integers \(z_1,..., z_d\) and it is asked whether \(g_1^{n_1} ... g_d^{n_d} = 1\) holds in the underlying group. Moreover, we prove that the knapsack problem for \(BS(1,q)\) is \(NP\)complete. In the knapsack problem, the input consists of group elements \(g_1,…, g_d, h\), and it is asked whether the equation \(g_1^{x_1} ... g_d^{x_d} = h\) (where the \(x_i\) are variables ranging over the natural numbers) has a solution.

Meeting #203
Vitaly Roman'kov
"Positive elements and membership problem for submonoids of finitely generated nilpotent groups of class 2"
Abstract. We show that there is a finitely generated group \(G\) of class \(2\) with undecidable membrship problem for finitely generated submonoids. Thus the wellknown problem by M. Lohrey and B. Steinberg is solved. A criterion of potentially positivity of a set of elements of a free nilpotent group \(\mathbb{N}\) of class \(2\) is also given. This criterion is used for a presentation of some sufficient conditions for decidability of the membership problem for a submonoid of \(\mathbb{N}\).

Meeting #202
Albert Garreta
"Word equations with Monte Carlo Tree Search and blackbox string solvers"
Abstract. Word equations have long been a relevant problem both from a theoretical and an applied perspective. Concerning the latter, an increased effort has been made over the years in order to develop practical algorithms for (partially) solving them, since word equations arise in many applications such as software analysis, cybersecurity, or even bioinformatics. In this talk we propose new solvers which leverage recent successful general techniques from the field of artificial intelligence and, possibly, already existing heuristicbased wordequation solvers. We propose and test two algorithms: one which uses any solver as a blackbox and attempts to improve its performance, and another which tackles word equations with essentially no domainspecific heuristic.

Meeting #201
Maksim Zhukovskii
(MIPT)"First order complexity of subgraph isomorphism"
Abstract. Given a graph F, what is a minimum number of variables (or a minimum quantifier depth) of a first order sentence about graphs that defines containment of a subgraph isomorphic to F? Clearly, the answer is the number of vertices of F both for the number of variables and the quantifier depth. However, the problem becomes nontrivial if the inputgraph is connected. It is also far from trivial when we restrict ourselves with induced subgraphs isomorphic to F. In the talk, we will discuss the current progress in both questions.

Meeting #200
Andrey Nikolaev
(Stevens Institute of Technology, Hoboken, USA)"Parameterized complexity of the word search problem in the BaumslagGersten group"
Abstract. Complexity of algorithmic problems can be studied as a function of the size of the input and a parameter that describes the size of the answer. This gives rise to the notion of parameterized complexity. In the case of the word problem and the word search problem in groups, the area of a van Kampen diagram can serve as a parameter. We consider the word search problem in the BaumsagGersten group. Among other features, this onerelator group is remarkable for its nonelementary Dehn function. Nevertheless, we show that the parameterized complexity of the word search problem in this group is polynomial in the size of the input and the parameter. (Joint work with A.Miasnikov.).

Meeting #199
Marina Schwidefsky
"On the structure of quasivariety lattices II"
Abstract. Further results on the complexity of quasivariety lattices will be presented. In particular, it will be demonstrated that a number of classical quasivarieties contain a continuum of subvarieties for which some algorithmic problems are unsolvable.

Meeting #198
Vitaly A. Roman'kov
"Embeding theorems for solvable groups"
Abstract. It is proved that any finitely generated solvable group of step l is isomorphically embeddable in a 4generated solvable group of step l + 1. Thus the problem of MikayelyanOlshansky is positively solved. It will also be explained what is the “magic square” and how can it be used in cryptography.

Meeting #197
Anton Menshov
(Stevens Institute of Technology, USA)"Attack on Kayawood protocol: uncloaking private keys"
Abstract. We analyze security properties of a twoparty keyagreement protocol recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels, called Kayawood protocol. At the core of the protocol is an action (called Emultiplication) of a braid group on some finite set. The protocol assigns a secret element of a braid group to each party (private key). To disguise those elements, the protocol uses a socalled cloaking method that multiplies private keys on the left and on the right by specially designed elements (stabilizers for Emultiplication).
We present a heuristic algorithm that allows a passive eavesdropper to recover Alice's private key by removing cloaking elements. Our attack has 100% success rate on randomly generated instances of the protocol for the originally proposed parameter values and for recent proposals that suggest to insert many cloaking elements at random positions of the private key. Implementation of the attack is available on GitHub.
The talk is based on the joint paper with Matvei Kotov and Alexander Ushakov. 
Meeting #196
Denis Ovchinnikov
(Stevens Institute of Technology, USA)"Diophantine problems in rings and groups"
Abstract. For a fixed algebraic structure, the Diophantine problem over this structure it is a question of the existence of an algorithm that determines the solvability of systems of equations over this structure. Classic examples of such problems are, in particular, the MakaninRazborov algorithm, showing solvability for free groups, and the 10th Hilbert problem showing undecidability for a ring of integers. We consider Diophantine problems over finitely generated commutative rings and groups that may be associated with nilpotent. We prove that in such systems the unsolvability of diophantine problems can be reduced to the insolubility of the diophantine problem over some ring of integers of some numerical field. The question of (un) solvability of diophantine problems over rings is a famous open hypothesis. We also show that for many groups the reduction is to the Diophantine problem over rational integers, which establishes unsolvability of the diophantine problem for such groups. Examples of such groups include free solvable groups, generalized Heisenberg groups, and many matrix groups. Report based on articles coauthored with Alexei Georgievich Myasnikov and Albert Garreta

Meeting #195
Marina Schwidefsky
(Math Center in Akademgorodok)"On the structure of quasivariety lattices"
Abstract. A quasivariety is a class of systems of the same type of algebraic systems defined by a certain set of quasiidentities. For an arbitrary quasivariety, the set of all its subquasivarieties forms a complete lattice with respect to the inclusion of classes. Lattices isomorphic to lattices of this kind are called quasivariety lattices. The report will present recent results on the structure of such lattices, as well as some open questions.

Meeting #193
Alexander Rybalov
"Generic aproach: perspectives and problems"

Meeting #192
Alexander N Grishkov
"Variety of Steiner loops generated by the simple loop of rank 10"

Meeting #191
Artem Shevlyakov
"Another algebraic aproach to machine learning"

Meeting #190
Alexey Myasnikov
(Stevens Institute of Technology)"Open problems in universal and noncommutative algebraic geometry"

Meeting #189
Denis Solomatin
(Omsk State Pedagogical University)"The study of algebraic structures using the programs Prover9 and Mace4"
Abstract. Based on the materials of Chapter 5 of the book “Mathematical Education in the Digital Age” https://arxiv.org/pdf/1908.06479.pdf (Rob Arthan, Paulo Oliva).

Meeting #188
Alexander Treyer
"Graph Extension Properties"
Abstract. In the theory of countable simple graphs, the central role is played by the extension property for graphs, which is as follows: for any two disjoint sets of vertices X and Y there exists a vertex v not belonging to X and Y such that v is connected to all vertices from X and not connected to all vertices from Y. The only countable graph satisfying the extension property is the Rado graph. The report will identify weakened versions of the extension property and present countable graphs that are not isomorphic to the Rado graph and on which weak versions of the extension property for graphs are satisfied.

Meeting #187
Artyom Shevlyakov
"Algebraic objects in machine learning"

Meeting #186
Alexey Myasnikov
(Stevens Institute)"Diophantine problem in metabelian groups"
Abstract. I will talk about Diophantine problem in metabelian groups. In particular, I will try to decidable precisely where the problem is decidable and where undecidable.
The report will be via Skype. 
Meeting #185
Denis Ovchinnikov
(Stevens Institute)"Random nilpotent groups"

Meeting #184
Alexander Rybalov
"Generic complexity and cryptography"
Abstract. An overview of the results on the generic complexity of cryptographic problems will be given. Some open issues will be formulated.

Meeting #183
Alexey Myasnikov
(Stevens Institute of Technology)"Groups and cryptography: problems, questions, and ideas"

Meeting #182
Vitaly A. Roman'kov
"A method for improving wellknown schemes of algebraic cryptography"

Meeting #181
Vladimir N. Remeslennikov
Agenda:

About the work of the Computer Science seminar in the 201920 school year.

International Mathematical Centers.

On some problems connected with finite combinatorics.
