# Omsk Algebraic Seminar

### "Sublinear time algorithms in (semi)groups"

Abstract. We are going to discuss what can be done in sublinear time (in the "length" of an input); in particular, without reading the whole input but only a small part thereof. One well-known example is deciding divisibility of a decimal integer by $$2$$, $$5$$, or $$10$$: this is done by reading just the last digit. We will discuss some less obvious examples from (semi)group theory.

### "IBN-varieties of algebras"

Abstract. The concept of a variety with IBN (invariant basic number) property first appeared in the ring theory. But we can define this concept for an arbitrary variety of universal algebras with an arbitrary signature. The proof of the IBN propriety of some variety is very important in universal algebraic geometry. This is a milestone in the study of the relation between geometric and automorphic equivalences of algebras of this variety. We prove very simple but very useful for the study of IBN properties of different varieties theorems. We will consider some applications of these theorems. We will consider many-sorted universal algebras as well as one-sorted. So, all concepts and all results will be generalized for the many-sorted case.

### "Equationally noetherian graphs and hypergraphs"

Abstract. A simple graph is called equationally noetherian if any system of equations is equivalent to its finite subsystem. It isn't hard to notice that a simple graph is equationally noetherian if and only if it is equationally noetherian in one variable equations. Based on this property we described all equationally noetherian graphs with help of forbidden subgraphs (joint with Ivan Buchinsky). Also several examples of hypergraphs will be presented that are not equationally noetherian but equationally noetherian in one variable equations.

### "Hardness of equations over finite solvable groups under the exponential time hypothesis"

Abstract. The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in 2002. They showed that this problem is in polynomial time for nilpotent groups, while it is $$NP$$-complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups G having a nilpotent normal subgroup H with nilpotent factor $$G/H$$. In this talk I will show that such normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails. Moreover, the same hardness result applies to the equation identity problem. The talk is based on joint work with Pawel Idziak, Piotr Kawalek, and Jacek Krzaczkowski.

### "Generic complexity of the identity problem over finite groups and semigroups"

Abstract. The problem of checking identities in algebraic structures is the one of the most fundamental problem in algebra. For finite algebraic structures this problem can be decidable in polynomial time, or hard (co-$$NP$$-complete). In this talk I present generic polynomial algorithms for the identity problem in all finite groups and for some monoids and semigroups. These algorithms work in the cases when the problem is co-$$NP$$-complete.

### "Relative quasivarieties of Hasse diagrams with a single zero"

Abstract. The present work is devoted to the category of Artinian partially ordered sets $$K$$ ($$APOS$$), which is defined as follows: any strictly decreasing chain of elements terminates at a finite number.

### "Centralizer dimension and equationally noetherian groups"

Abstract. In 1999th G.Baumslag, A.Miasnikov and V.Remeslennikov formulated the following problem:

Let $$L$$ be the language of group theory, $$G$$ be a group and $$L_G$$ be the language of group theory with a set of constants from the group $$G$$. Let the group $$G = <G, L_G>$$ be equationally noetherian over one variable equations ($$1$$-equationally noetherian) Does it follow that the group $$G$$ is equationally noetherian?

An example of a nilpotent group will be presented, which is $$1$$-equationally noetherian but is not equationally noetherian in general. The proof will be based on the new results on a close relation between the concepts of centralizer dimension and noetherenes by equations for groups.

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

### "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 p-adic numbers is especially interesting, as well as the rings of p-adic 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.

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