Upcoming meeting:

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.
Latest announcements:

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.