Journées nationales 2008

Les journées du GDR IM se tiendront cette année­ du 24 au 25 janvier 2008 à l’université Paris 7 sur le nouveau campus Paris Rive-Gauche.

 Les transparents sont disponibles ici­

­Jeudi 24 janvier 2008
_{[cliquez sur les noms d’auteurs pour lire les résumés]}

11:00 – 12:00 : Conférence invitée : Mike Paterson (Warwick) « Overhang Bounds »
12:00 – 12:45 : Olivier Laurent (PPS) GT GEOCAL et LAC « Sémantique des jeux : de la programmation à la logique »

12:45 – 14:45 : Déjeuner

14:45 – 15:30 : Boris Adamczewskii (Institut Camille Jordan) GT Sda2 et Comatege  « Mots infinis et nombres transcendants »
15:30 – 16:15 : Ludovic Perret (LIP6) GT C2 « Cryptographie et calcul symbolique »

16:15 – 17:00 : Pause

17:00 – 17:45 : Sylvain Gravier (Institut Fourier) GT Graphes « Questions extrêmales : combinatoire ou probabilités ? »
17:45 – 18:30 : Discussion sur le GDR

19:00 – 22:00 : Buffet-cocktail (sur place)

Vendredi 25 janvier 2008

09:00 – 10:00 : Conférence invitée : Peter Bürgisser (Paderborn) « Smoothed analysis of condition numbers »
10:15 – 11:00 : Iordanis Kerenidis (LRI) GT IQ « An Introduction to Quantum Information Theory »
11:00 – 11:30 : Pause

11:30 – 12:15 : Damien Jamet (LORIA) GT Géométrie Discrète « Combinatoire des mots et géométrie discrète »
12:15 – 13:00 : Danièle Gardy (PRISM) GT ALEA « Expressions booléennes aléatoires; application à la probabilité et complexité ­de fonctions booléennes »

13:00 – 14:45 : Déjeuner

14:45 – 15:30 : Luc Segoufin (INRIA Saclay) GT CMF et Jeux « Automates et logiques pour mots sur un alphabet infini »
15:30 – 16:15 : Jean-Guillaume Dumas (LJK) GT Calcul Formel « Calcul algébrique haute performance »
 

Résumés

Mike Paterson
Titre : Overhang Bounds
Résumé : How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. Recently, we (Paterson and Zwick) constructed n-block stacks with overhangs of order n^{1/3}, exponentially better than previously thought possible. The latest news is that we (Paterson, Peres, Thorup, Winkler and Zwick) can show that order n^{1/3} is best possible, resolving the long-standing overhang problem up to a constant factor.

I shall review the construction and describe the upper bound proof, which illustrates how methods founded in algorithmic complexity can be applied to a discrete optimization problem that has puzzled some mathematicians and physicists for more than 150 years.

Olivier Laurent
Titre : Sémantique des jeux : de la programmation à la logique
Résumé : La sémantique des jeux a permis de nombreuses avancées dans la  construction de modèles dénotationnels de traits de programmation et de systèmes logiques.  Partant d’une présentation intuitive de la représentation dans les jeux de différentes primitives de programmation (noyau fonctionnel, contrôle, références, etc.), nous montrerons comment restreindre ou étendre ces modèles pour interpréter exactement le langage que l’on  souhaite. Grâce au transfert de ces techniques à la logique par la correspondance de Curry-Howard, nous présenterons un modèle exact  (plein et fidèle) de la logique classique du premier ordre.

Boris Adamczweski
Titre : Mots infinis et nombres transcendants
Résumé : Les mots finis ou infinis apparaissent naturellement en théorie des nombres dès que l’on souhaite représenter tous les éléments d’un certain ensemble (nombres entiers, réels, p-adiques, séries formelles…) de façon unifiée. Ainsi, les développements décimaux, binaires ou en fraction continue permettent d’associer à tout nombre réel une unique suite finie ou infinie de chiffres.

Dans cet exposé, on s’intéressera plus spécifiquement au cas du développement des nombres réels dans une base entière. Il est malheureusement difficile d’obtenir des renseignements sur les suites des chiffres correspondant à des constantes mathématiques classiques comme pi, zêta(3),  ou encore racine de 2.

On montrera comment certaines propriétés combinatoire d’un mot infini permettent de révéler certaines propriétés diophantiennes du  nombre réel qui lui est associé. Cette aproche permet, in fine, d’obtenir des résultats sur la structure combinatoire des mots infinis associés aux nombres algébriques irrationnels.

Ludovic Perret
Titre : Gröbner Bases in Cryptography : Selected Topics
Résumé : Research in cryptography is obviously characterized by a sequence of defenses and attacks. Thus, in order to evaluate the security of cryptographic schemes, strong and new efficient methods have to be developped. In this talk, we will focus our attention  to a general technique called  algebraic cryptanalysis.  The idea is to model a cryptographic primitive as a set of algebraic equations. The system is constructed in such a way as to have a  correspondence between the solutions of this system, and a secret information of the considered primitive. Once this modeling is done, the problem is then to solve the algebraic system (or to evaluate the difficulty of solving such a system). Up to now, Gröbner bases appear to yield the best algorithms to do so.

In this talk, we will present two applications of Gröbner basis based cryptanalysis. First, we will consider algebraic cryptanalysis against block ciphers. After having briefly reviewed the main results in this domain, we will focus our attention to  two families of block ciphers, namely Flurry and Curry respectively.
The encryption process of these ciphers can  be easily described by a set of algebraic equations; being then targets of choices for algebraic attacks. In a second  part, we will present a new  algorithm for decomposing multivariate polynomials of an arbitrary degree.
This problem, also known as the Functional Decomposition Problem (FDP), is  a classical problem in computer algebra. This works was initially motivated  by a cryptographic application, namely the cryptanalysis of a  multivariate public key scheme called 2R− , based on the  assumption that FDP is a hard problem. 

Sylvain Gravier
Titre : Questions extrêmales : combinatoire ou probabilités ?
Résumé : Les questions extrêmales abordées dans cet exposé concernent d’une part des problèmes de type Ramsey: Existe-t-il un nombre R tel que toutes colorations des arêtes du graphe (ou hypergraphe) complet d’ordre R assure l’apparition d’une « sous-structure » monochromatique ?
L’exemple classique de sous-structure est le triangle. D’autre part, des problèmes plus récents reliés à l’existence de codes correcteurs ayant des propriétés d’identification (codes identifiants, codes superimposés, …).  Pour ces deux types de problèmes, la méthode probabiliste a permis de donner des éléments de réponse. Cependant, dans la plupart des cas, des constructions combinatoires (explicites) restent à découvrir. Nous essaierons d’identifier la frontière entre combinatoire et probabilité en lien avec ce type de problèmes. 

Peter Bürgisser
Titre : Smoothed analysis of condition numbers
Résumé : The running time of many iterative numerical algorithms is dominated by the condition number of the input, a quantity measuring the sensitivity of the solution with regard to small perturbations of the input. Examples are iterative methods of linear algebra, interior-point methods of linear and convex optimization, as well as homotopy methods for solving systems of polynomial equations. Spielman and Teng introduced in 2001 the seminal concept of smoothed analysis, which arguably blends the best of both worst-case and average-case analysis of algorithms. This led to a much better understanding of the success of the simplex method in practice.
In the talk we overview general geometric techniques for providing smoothed analysis estimates for conic condition numbers and discuss their applications to linear and polynomial equation solving as well as to linear programming. 

Iordanis Kerenidis
Titre : An Introduction to Quantum Information Theory
Résumé : Quantum computation and information studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. Although, it is a rather new research area, there have been numerous surprising results, for example Shor’s algorithm for factoring large numbers and the existence of unconditionally secure key distribution, that make quantum information a very exciting and fundamental research field. In this talk, we give an introduction to the theory of quantum information by drawing comparisons to classical probability theory. We start by defining the carrier of quantum information, the quantum bit, and proceed to describe a notion of entropy for quantum states. Quantum information theory is a rich mathematical theory that can also be used as a powerful tool for the study of classical information.
We show how to use such techniques in order to prove an optimal lower bound for Locally Decodable Codes. These codes are important in Complexity Theory and especially the area of Probabilistically Checkable Proofs (PCPs). 

Damien Jamet
Titre : Combinatoire et Topologie des Objets Discrets Linéaires
Résumé : Dans cet exposé, je m’intéresserais aux propriétés combinatoires et topologiques des objets fondamentaux de la géométrie discrète, à savoir les hyperplans discrets. A partir de quelques exemples, je montrerai comment la combinatoires des mots la dynamique symbolique et l’arithmétique permettent de répondre à de nombreuses questions relatives à ces objets.
 

Danièle Gardy
Titre : Expressions booléennes aléatoires, probabilités et complexités
Résumé : Toute fonction booléenne peut être représentée par une expression booléenne aléatoire, c’est-à-dire par un arbre respectant certaines règles de formation et d’étiquetage. Une loi de probabilité définie sur ces arbres se traduit alors en loi de probabilité sur l’ensemble des fonctions booléennes. Nous considérerons dans cet exposé divers modèles d’expressions booléennes aléatoires, et les lois de probabilité que ces modèles induisent sur les fonctions booléennes. Nous nous intéressons en particulier aux liens entre probabilité et complexité (i.e. taille minimale d’un arbre représentant la fonction). Nous montrons par exemple que, dans un certain nombre de modèles, les tautologies sont presque sûrement « simples ». Nous pouvons caractériser des modèles dans lesquels la probabilité de la fonction constante 1 (i.e. la probabilité des tautologies) est d’ordre 1/n, n étant le nombre de variables booléennes (vs. 1/2^n pour une distribution uniforme des fonctions booléennes).
Les problèmes de satisfaction de contraintes (CSP) peuvent aussi rentrer dans ce cadre: il s’agit ici d’étudier la probabilité de la fonction constante O.

Luc Segoufin
Titre : Automates et logiques pour mots sur un alphabet infini
Résumé : En vérification automatique de programme on est confronté à deux sources de difficultés (qui ne sont pas indépendantes) génèrant des exécutions infinies: la récursion et les valeurs que peuvent prendre les variables. La plupart des travaux se sont attaqués essentiellement au premier cas en traitant des propriétés concernant le flux de contrôle.  Dans cet exposé on va présenter une approche permettant de traiter le second cas pour pouvoir traiter des propriétés concernant le flux de données. Cette approche permet aussi de résoudre des problèmes d’optimisation en bases de données. Pour cela on considèrera des mots sur un alphabet infini afin de coder par exemple les valeurs successives d’une variable. On présentera ensuite plusieurs logiques et plusieurs modèles d’automates dont le test du vide est décidable. 

Jean-Guillaume Dumas
Titre : Compromis temps/mémoire en algèbre linéaire dense dans des corps finis sous titre == le cas de la multiplication de matrices à coefficients dans un petit corps fini non premier.
Résumé : Ces dernières décennies, de nombreux efforts ont été faits pour réduire les problèmes d’algèbre linéaire exacte à la multiplication de matrice afin de fournir des algorithmes de complexité algébrique asymptotique optimale. Par ailleurs il semble clair que les techniques modulaires comme les restes chinois ou les remontées p-adique sont indispensables pour obtenir des complexités binaires et des implantations efficaces de ces algorithmes pour des calculs exacts sur les entiers, les rationnels, les polynômes etc. Par conséquent, l’algèbre linéaire dense dans des corps finis et plus spécialement la multiplication de matrices est un noyau important d’une bibliothèque d’algèbre linéaire exacte comme LinBox.

Dans cet exposé nous montrons différents aspects de cette réalisation permettant l’obtention de bonnes performances : un compromis temps-mémoire dans l’utilisation de l’algorithme Strassen-Winograd combiné à l’utilisation de routines numériques permet d’optimiser les accès mémoire et le nombre d’opérations arithmétiques ;  un compromis temps-mémoire pour la multiplication de polynômes modulaires permet de gagner un ordre de grandeur pour l’arithmétique des corps finis et les conversions vers les routines numériques.