Alexei Miasnikov  McGill University, Canadá.

            Complexities of Algorithms.

In this course  I am going to discuss some recent developments in asymptotic and computational algebra, and their applications to modern cryptanalysis.

I begin with "Generic complexity of algorithms" describing the complexity of algorithms on "most" or "generic" inputs. This type of complexity differs from the well-known  worst-case and average-case complexities. I will argue that the generic-case complexity is precisely the type of complexity required in cryptanalysis of modern cryptoschemes.

We shall continue with  "Random van Kampen diagrams and algorithmic problems in groups". I am going to present some new "generically fast" algorithms for solving the word, conjugacy, and mebership  problems in groups. The algorithms are based on some recent  results on generic properties of van Kampen diagrams. For example, I will show that generic van Kampen diagrams of finitely presented  groups are "hyperbolic". This sheds some light on security  of cryptosystems based on the word and conjugacy problems.

Finally, we will study "Asymptotically dominant properties and subgroup attacks" focusing on asymptotic properties of subgroups of infinite groups.

It turns out "generic subgroups" quite often have very specific properties that provide a basis for various subgroup attacks. I will discuss on how one could avoid the attacks choosing the subgroups carefully.