Upcoming meeting:
-
Meeting #202
Albert Garreta
"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.
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 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.
-
Meeting #200
Andrey Nikolaev
(Stevens Institute of Technology, Hoboken, USA)"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.).
-
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 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.
-
Meeting #197
Anton Menshov
(Stevens Institute of Technology, USA)"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.