Jan 10

Ecole de printemps d’informatique théorique 2013

ECOLE DE PRINTEMPS D’INFORMATIQUE THEORIQUE 2013
Algorithmique des réseaux euclidiens et applications
Autrans (Isère), 18-22 mars 2013

[Merci à tou(te)s de faire suivre aux personnes susceptibles d’être
intéressées hors GDR IM]

Comité d’organisation : Guillaume Hanrot (LIP, ENS Lyon), Damien Séon
(LIP, ENS Lyon), Damien Stehlé (LIP, ENS Lyon)

Comité scientifique des EPIT : Roberto Amadio (Paris 7 / PPS),
Pierre-Louis Curien (CNRS/PPS), Guillaume Hanrot (ENS Lyon/LIP),
Frédéric Magniez (CNRS/LIAFA — président), Jean Mairesse
(CNRS/LIAFA), Anca Muscholl (U. Bordeaux / LaBRI).
—————————————————————————
L’Ecole de Printemps d’Informatique Théorique est une institution dans
le domaine de l’Informatique Théorique en France. L’Ecole s’est
développée sous la direction de Maurice Nivat en 1973. Durant ses 39
ans d’existence, elle a couvert un large spectre des thèmes porteurs
en informatique théorique et elle représente maintenant le lieu de
rencontre par excellence pour les nouvelles générations de chercheurs
du domaine.

L’édition 2013 s’intéressera à l’algorithmique des réseaux euclidiens
et à ses applications. Les réseaux euclidiens (informellement, les
grilles de points régulièrement espacés dans un espace euclidien) sont
un outil classique en informatique théorique. Un grand nombre de
problèmes algorithmiques classiques et importants (programmation
linéaire entière, factorisation de polynômes à coefficients
rationnels, détection de relations linéaires entre nombres réels, …)
peuvent se ré-exprimer en termes de réseaux euclidiens, et être
résolus en trouvant des vecteurs de petite taille dans des réseaux
bien choisis.

L’algorithmique des réseaux euclidiens est en plein essor. D’importants
progrès ont été réalisés dans le cadre de la compréhension du coût de la
résolution des problèmes algorithmiques centraux (comme calculer des
vecteurs courts de réseaux arbitraires).

Mais surtout, certaines applications se développent à un rythme
effréné. Citons en particulier la cryptographie reposant sur les
réseaux : il s’agit d’un vaste ensemble de primitives cryptographiques
(chiffrement, signatures digitales, protocoles d’identification) dont
la sécurité repose sur la difficulté de problèmes algorithmiques
s’exprimant à l’aide des réseaux. Les raisons de cet engouement sont
multiples : potentiel d’efficacité important, preuves de sécurité sous
un nombre restreint d’hypothèses bien étudiées, résistance apparente
au calcul quantique, et fonctionnalités nouvelles. Une de ces
nouvelles fonctionnalités est le chiffrement homomorphe, permettant
d’effectuer des calculs en n’ayant accès qu’aux données chiffrées,
dont les applications potentielles (à long terme) semblent à ce jour
considérable.

D’autres domaines applications seront abordés : communications
(eg. codes pour les communications sans fil), programmation linéaire
entière, arithmétique des ordinateurs (eg. approximation de fonctions
en vue de leur évaluation efficace). Un cours sera également consacré
à l’analyse d’algorithmes en lien avec la réduction de réseaux.

Orateurs invités :
J.-C. Belfiore (Télécom ParisTech, Paris)
N. Brisebarre (CNRS, Lyon)
D. Dadush (NYU, New York)
G. Hanrot (ENS Lyon, Lyon)
V. Lyubashevsky (INRIA, Paris)
D. Stehlé (ENS Lyon, Lyon)
B. Vallée (CNRS, Caen)

Informations pratiques :
————————
L’école se tiendra à Autrans (Isère) au village vacances des Escandilles,
www.escandille.com.  Une arrivée est prévue le dimanche 17 mars, et la
fin de l’école est prévue le vendredi 22 mars après le déjeuner.

Les frais d’inscription prévisionnels devraient tourner autour de 400
euros, incluant l’hébergement en pension complète.

Calendrier prévisionnel :
————————-
* Pré-inscriptions du 15 décembre au 15 janvier
* Inscription définitive avant le 9 mars.