Théorie Combinatoire des groupes, algorithmique et cryptographie

Présentation générale :

Présentation de la semaine :

Orateurs principaux :

• David Bessis (ENS Paris)
• Jon McCammond (UCSB)
• Denis Osin (CUNY)
• Vladimir Shpilrain (CUNY)

• José Burillo
• Robert Gilman
• Olga Kharlampovich
• Alexei Miasnikov
• Géraud Sénizergues
• Bert Wiest

Comité scientifique :

• Patrick Dehornoy (Caen)
• Juan Gonzales-Meneses (Sevilla)
• Ilya Kapovich (Urbana-Champaign)
• Pascal Weil (Labri, Bordeaux)

Comité local :

• Hamish Short (LATP, Université de Provence)
• Thierry Coulbois (LATP, Université Paul Cézanne)
• Jean-Philippe Préaux (LATP, École de l'air)

Inscription :

Soutien financier :

Programme détaillé

• Vladimir Shpilrain (CUNY)
  Applications of group theory in cryptography
  

  Although the security of the Internet does not appear to be threatened at this time because of the weaknesses of the existing cryptographic protocols such as RSA, it seems prudent to explore possible enhancements and replacements of such protocols which depend on finite commutative groups. This is the basic objective of the present mini-course. Non-commutative groups were introduced into public-key cryptography by Wagner and Magyarik more than 20 years ago, but only relatively recently did this direction get serious attention of professional cryptographers worldwide, due to seminal work of Anshel, Anshel, and Goldfeld (1999). Since then, a very active research in non-commutative cryptography is going on, and we are going to describe these new promising research avenues, most of which employ classical as well as modern combinatorial group theory, with a focus on algorithmic problems and their complexity.

  Tentative titles of the four 45-minute lectures are:
  1. Public key protocols based on non-abelian groups
  2. Underlying problems: nothing is what it seems
  3. Cryptanalysis: employing statistical and asymptotic group theory
  4. Using decision problems in public key cryptography
  
  
  
• David Bessis (ENS Paris) Garside Groupoids

  The notion of Garside group was invented by Dehornoy and Paris to axiomatize properties of spherical type Artin groups. Following new ideas by Krammer and Digne-Michel, we'll explain how this theory is much better understood in a categorical setup, where groups are replaced by groupoids. In particular, a beautiful theorem by Bestvina (based on hyperbolic features of spherical type Artin groups) becomes even more beautiful when restated in terms of equivalences of categories. (Don't be frightened by this description: the aim is to be understood by non-experts!)

• Oleg Bogopolski Subgroups of small index in Aut (F_n) and Kazhdan's property (T)

  Does the group Aut(F_n) possess the Kazhdan property (T)for n>3? Does there exist a subgroup of finite index in Aut(F_n), n>3, which can be mapped onto Z? If the answer to the second question is positive, then the answer to the first question is negative. We will discuss possible candidates to answer the second question in positive.

• Murray Elder
  Asymptotic properties of subgroups of Thompson's group F

  Suppose you picked two elements of a group G "at random";, and asked what subgroup they generate. What is the chance it would be free, abelian, or G itself? If G was a free group, then since finitely generated subgroups of free groups are free, the answer isn't so exciting. But what if G were Thompson's group F? Jen Taback(Bowdoin) and I asked this question and have some partial answers. First we had to decide how to pick elements at random, and how to compute probabilities of being certain subgroups. We use the notion of "asymptotic density" of Miasnikov et al.

• Olga Kharlampovich
  Groups acting on trees The general theory of groups acting on trees was originated by Bass and Serre. In this talk I will discuss some methods and techniques designed to deal with groups acting freely on $\Lambda$-trees. These methods were extensively, though sometimes implicitly, used in our (joint with A. Myasnikov) solution of the Tarski's problems about the elementary theory of a free group. It seems it is worthwhile to introduce them explicitly. Our key players in this area are infinite non-Archimedean words and Elimination Processes. This talk is based on joint results with A. Myasnikov, V. Remeslennikov, D. Serbin.
  
  
• Denis Osin
  Lacunary hyperbolic groups The talks will be based on the joint paper with A. Olshanskii and M. Sapir. We call a group lacunary hyperbolic if one of its asymptotic cones is an R--tree. I will discuss:
  1. A characterization of lacunary hyperbolic groups as direct limits of Gromov hyperbolic groups satisfying certain restrictions on the hyperbolicity constants and injectivity radii.
  2. Common properties of lacunary and ordinary hyperbolic groups.
  3. Examples of "exotic" lacunary hyperbolic groups (non--virtually cyclic amenable, infinite simple, infinite periodic, etc.)
  4. The answer to Gromov's question of whether the fundamental group of any asymptotic cone of any finitely generated group is either trivial or uncountable. The solution is based on the study of central extensions of lacunary hyperbolic groups.
  5. Solutions of various problems about cut points in asymptotic cones and divergence of geodesics in Cayley graphs of finitely generated groups.
  
  
  
• Enrique Ventura
  The first part of Whitehead's algorithm made polynomial (Joint work with P. Weil and A. Roig) The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word (a cyclic word or a finitely generated subgroup) in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier (classical) algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem (to decide whether a word is an element of some basis of the free group) and the free factor problem can also be solved in polynomial time. The new algorithm is surprisingly simple, making use of a classical argument about Whitehead automorphisms and Whitehead graphs, and the classical Max-Flow Min-Cut algorithm for graphs.
  
  
• Alexei Miasnikov
  Free actions and Non-Archimedean words In this talk I am going to discuss a new approach to group actions via infinite Non-Archimedean words. The key idea here is that groups acting freely on Lambda-trees behave themselves like the standard free groups if in the latter the finite words are replaced by their infinite Non-Archimedean analogs. For example, one can use an "infinite version" of Makanin-Razborov method to simplify presentations of groups given by generators and relators or apply finite Buchi-type automata to solve the membership problem in groups acting freely on suitable trees. As an illustration I will describe the algebraic structure of groups acting freely on Z^n-trees. This talk is based on joint results with O.Kharlampovich, V.Remeslennikov, and D.Serbin.
  
  
• Alexei Miasnikov (McGill and Algebraic Cryptography Center at Stevens Institute)
  Asymptotic group theory and cryptanalysis Is group-based cryptography a cutting edge or a dead-end of cryptography? Is our knowledge of groups sufficient to make good cryptosystems, or, perhaps, groups are so widely studied that group-based cryptosystems have no chance to survive? It turns out that rigorous cryptanalysis of some well-known group-based cryptosystems lead to several completely new highly non-trivial problems in group theory. The main focus of this talk will be on some of these problems. In particular, I will discuss asymptotic properties of subgroups of infinite groups and generic amplification of undecidable problems.
  
  
• Bert Wiest (Rennes)
  The conjugacy problem in right-angled Artin groups and their subgroups We prove that the conjugacy problem in right-angled Artin groups and a large class of their subgroups can be solved in linear time. Some of this talk is joint work with J.Crisp, some with J.Crisp and E.Godelle.
  
  
• Jon McCammond (UCSB)
  Coxeter groups and Artin groups
  
  

Dernière mise à jour le lundi 2 février 2007
Page créée et mise à jour par Thierry Coulbois