Selected Talks

2009

 

Limit Algebras [pdf]

Abstract: Fully residually free (limit) groups play an important part in the recent solution of Tarski's problems about free groups. What are limits of other groups? Why are they interesting? What common properties do they have? These are the main questions I am going to discuss in the talk. I will touch on the general theory of limit algebras (groups, semigroups and rings) and then discuss some particular examples.

Mathematics of Commutator Key Exchange (AMS Annual Meeting, Washington DC, January 7, 2009). [pdf]

Abstract: I am going to discuss some recent developments in non-commutative cryptography. The main focus will be on mathematical problems that arise here, and how solutions to these problems may affect security of various public key exchange schemes. I will discuss on how the classical algebraic algorithmic problems are used in cryptography, and what should be avoided; why undecidable decision problems may play a part in cryptanalysis of real cryptosystems, and what kind of practical knowledge one can get from asymptotic methods. Most of the ideas that occur here are quite general, but I will try to explain them on one particular example - the commutator key exchange schemes based on groups.

Group presentations: infinite versus finite (University of Nebraska-Lincoln, May 21, 2009). [pdf]

Abstract: The classical algorithmic problems in combinatorial group theory deal with finite presentations of groups. Is it really necessary, or desirable, or just a burden? What are "good" (finite or infinite) presentations of a group? How one can find them? Is computing with infinite presentations feasible? These are the main questions I am going to touch on in the talk. In particular, I will discuss situations when infinite presentations give clear advantages over the finite ones. On the technical side the focus will be on modern rewriting techniques (Knuth-Bendix and infinite rewriting systems) and their relations with presentations (Stallings' pregroups), and on various compression tools.

Around Tarski and Beyond (Montreal, CRM Colloquium, January 30, 2009). [pdf]

Abstract: in this talk I am going to discuss recent solutions of Tarski's problems on elementary theory of free groups and their amazing relations to group theory, symbolic dynamics, topology, and computer science.

2004

Complexity of computations and cryptography, Microsoft Research (Redmond, WA, November 2004). [.pdf]

Abstract: Applications of mathematical methods to cryptography is one of the most rapidly developing areas of interdisciplinary research which attracts a lot of interest among mathematicians across the borders. Current situation with information security unambiguously indicates that such interest will be just getting stronger in the years to come. In this talk I am going to  discuss the feedback, the increasing influence of new methods and ideas coming  to mathematics from modern information technologies, the quest for paradigm change that we are experiencing now. It seems that we are going to witness some fundamental changes in our perception of algorithmic mathematics in the very near future. What are these changes, what kind of new interesting problems arise here, what is the  role of "experimental mathematics" (if any)  - these are the questions I would like to touch on.

 

Various faces of fully residually free groups and algorithmic problems, Workshop on Geometric Group Theory,  London Math. Soc., (Newcastle, June-July 2004). [.pdf]

Abstract: In this talk I am going to discuss various incarnations of finitely generated fully residually free groups. They appear naturally in algebraic geometry over groups, in the theory of equations over free groups, and play important part in the recent solution of the Tarski's problems. This gives a host of different techniques to solve various algorithmic problems. In particular, one can construct effectively JSJ decompositions of these groups and solve the isomorphism problem.