Journées du GDR Informatique Mathématique 2008

Journées du GDR Informatique Mathématique 2008

24/01/2008 - 11:00
25/01/2008 - 17:00

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­

­Programme des Journées du GDR Info­rmatique Mathématique

24 et 25 janvier 2008
, ­Université Paris 7

­

Lieu : Université Paris Diderot-Paris 7,Amphi 11 E, 3e étage
Halle aux farines, 10 - 16 rue Françoise Dolto 75013 Paris

Metro:  Bibliothèque F. Mitterrand ligne 14 et RER C

 

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 tire == 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.