|
GREYC
|
|
GREYC
|
Mots-clefs : algorithmique, complexité, analyse d'algorithmes, réseaux euclidiens, bases réduites, algorithme LLL, calcul formel, cryptographie, réseaux aléatoires, distribution uniforme, probabilités asymptotiques, lois 0-1, systèmes dynamiques.
Après avoir acquis de solides connaissances techniques en informatique à l'école d'ingénieurs, je me suis orienté par la suite vers le thème de l'algorithmique en arithmétique. De nombreuses applications en optimisation entière (calcul formel, cryptographie) se réduisent efficacement à la recherche d'un vecteur assez court dans un réseau euclidien. Pendant ma thèse, une grande partie de mon travail a consisté à proposer des algorithmes qui y parviennent plus rapidement en moyenne que l'algorithme de référence en la matière (l'algorithme LLL). Les résultats de ma thèse ont déjà fait l'objet de deux articles accéptés à ESA'99 et à LATIN'2000.
L'année précédente, je me suis initié à de nouvelles approches en analyse d'algorithmes et en tout premier lieu celle introduite par Brigitte Vallée: analyse dynamique . Il s'agit de considérer un algorithme dans le formalisme des systèmes dynamiques. Notre collaboration a déjà fait l'objet d'un article accépté à ICALP'2000, sur la complexité réaliste (en nombre d'opérations élémentaires) de l'algorithme d'Euclide et de ses variantes.
Je développe d'abord les 2 thèmes mentionnés ci-dessus, puis quelques perspectives de recherche.
