# Mathematical Center in Akademgorodok, Omsk Group Seminar

### "Knapsack and the power word problem in solvable Baumslag-Solitar groups"

Abstract.We show that the power word problem for a solvable Baumslag-Solitar 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.

### "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 well-known 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}$$.

### "Word equations with Monte Carlo Tree Search and black-box 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 heuristic-based word-equation solvers. We propose and test two algorithms: one which uses any solver as a black-box and attempts to improve its performance, and another which tackles word equations with essentially no domain-specific heuristic.

### "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 non-trivial if the input-graph 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.

### "Parameterized complexity of the word search problem in the Baumslag-Gersten 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 Baumsag--Gersten group. Among other features, this one-relator group is remarkable for its non-elementary 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.).

### "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.

### "Embeding theorems for solvable groups"

Abstract. It is proved that any finitely generated solvable group of step l is isomorphically embeddable in a 4-generated solvable group of step l + 1. Thus the problem of Mikayelyan-Olshansky is positively solved. It will also be explained what is the “magic square” and how can it be used in cryptography.

### "Attack on Kayawood protocol: uncloaking private keys"

Abstract. We analyze security properties of a two-party key-agreement 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 E-multiplication) 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 so-called cloaking method that multiplies private keys on the left and on the right by specially designed elements (stabilizers for E-multiplication).

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.

### "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 Makanin-Razborov 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 co-authored with Alexei Georgievich Myasnikov and Albert Garreta

### "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 quasi-identities. 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.

### "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).

### "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.

### "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.

### "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.