ER01: Randomized Algorithms (7-11 décembre)

Date : 7-11 décembre 2015

Intervenants: Joel Ouaknine, Ben Worrell et Stefan Kiefel (Oxford).
Contact local: Pascal Koiran

(Un résumé du contenu se trouve sur la version anglaise de cette page.)

Voici l’emploi du temps :

 

Monday: 9:30 – 11:30 am and 1:30 – 3:30 pm
Tuesday: 9 – 11:30 am, 1:30-3:30 pm and 4-6 pm.
Wednesday: 9-11:30 am and 1:30-3:30 pm.
Thursday: 9 am – 12:30 pm
Friday: 9 am – 12:30 pm and afternoon exam: 2 pm – 4 pm

ER01: Data Structures for Big Data

Date : 12-16 janvier 2015.

Enseignants: Michael Bender (Stony Brook University), Martín Farach-Colton (Rutgers and Tokutek), Samuel McCauley (Stony Brook University)

Description de l’école

Horaires des cours

Monday-Thursday:

  • morning lecture: 9:30am-11:30am

  • afternoon lecture: 1:30pm-3:30pm.

  • recitation/homework practice: 4pm-5pm.

Friday:

  • morning lecture: 9:30am-11:30am

  • afternoon exam:  2pm-5pm

Contact local : Frédéric Vivien.

Inscription

L’Inscription est gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le … (sera précisé plus tard) en cliquant ici, remplissant le formulaire et envoyant le mail. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternativement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à nicole.meftah@ens-lyon.fr, avec le sujet « Registration form — research school 1 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address: 

wishes to attend the research school « ER01: Advanced Data Structures », taking place at ENS Lyon, from Jan. 12 to Jan. 16, 2015.

ER02: Algorithms and Heuristics for Large-scale Data Sets

Date : 19-23 janvier 2015.

Page web dédiée

Enseignants: Nicolas Schabanel (Université Paris-Diderot), Alain Barrat et Bruno Gonçalves (Université Aix-Marseille)

Contact local : Marton Karsai

Inscription

L’Inscription est gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le … (sera précisé plus tard) en cliquant ici, remplissant le formulaire et envoyant le mail. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternativement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à nicole.meftah@ens-lyon.fr, avec le sujet « Registration form — research school 2 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address: 

wishes to attend the research school « ER02: « , taking place at ENS Lyon, from Jan. 19 to Jan. 23, 2015.

ER03: Static Analysis and Compilation

Date : 26-30 janvier 2015.

Page web dédiée

Enseignant: Fernando Magno Pereira (Univ Mineas Gerais, Brazil)

Contact local :  Laure Gonnord

Inscription

L’Inscription est gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le … (sera précisé plus tard) en cliquant ici, remplissant le formulaire et envoyant le mail. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternativement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à nicole.meftah@ens-lyon.fr, avec le sujet « Registration form — research school 3 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address: 

wishes to attend the research school « ER03: Static Analysis and Compilation », taking place at ENS Lyon, from Jan. 26 to Jan. 30, 2015.

ER01: Algorithmic Game Theory

Date : 9-13 décembre 2013.

Description de l’école et emploi du temps.

Contact local : Natacha Portier.

Inscription

L’Inscription est gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le 29 novembre en cliquant ici, remplissant le formulaire et envoyant le mail. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternativement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à nicole.meftah@ens-lyon.fr, avec le sujet « Registration form — research school 1 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address:

wishes to attend the research school « Algorithmic Game Theory », taking place at ENS Lyon, from Dec. 9 to Dec. 13, 2013.

ER02: Synchronous Approaches for Embedded Systems

Date : 13-17 Janvier 2014.

Site web.

Contact local : Laure Gonnord.

Inscription

L’Inscription est gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le 3 janvier en cliquant ici, remplissant le formulaire et envoyant le mail. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternativement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à nicole.meftah@ens-lyon.fr, avec le sujet « Registration form — research school 2 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address:

wishes to attend the research school « Synchronous Approaches for Embedded Systems », taking place at ENS Lyon, from Jan. 13 to Jan. 17, 2014.

ER03: Logic of Dynamical Systems

Orateurs : André Platzer et Sarah Loos.

Date: 20-24 Janvier 2014.

Page web.

Contact local : Filippo Bonchi

Inscription

L’Inscription est gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le 10 janvier 2014 en cliquant sur ce lien, remplissant le formulaire et envoyant le message électronique. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternativement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à nicole.meftah@ens-lyon.fravec le sujet « Registration form — research school 3 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address:

wishes to attend the research school « Logic for Dynamical Systems », taking place at ENS Lyon, from Jan. 20 to Jan. 24, 2014.

ER03: Problèmes de satisfaction de contraintes

21-25 Janvier 2013, ENS Lyon.

Orateurs: Manuel Bodirsky, Michael Pinsker.

Une description plus complète se trouve sur la version anglaise de cette page.

Lundi 21/01. Introduction. Exemples de CSPs de l’intelligence artificielle. Les formules primitives positives et des preuves de NP-difficulté. Des algorithmes efficaces. La conjecture de Feder et Vardi.

Mardi 22/01. L’approche d’algèbre universelle. La correspondance de Galois Inv-Pol, le noyau d’une structure, la conjecture de faisabilité, les operations cycliques.

Mercredi 23/01. Des CSPs sur des domaines infinis. Les limites de Fraïssé, le théorème de Ryll-Nardzewski. La correspondence Inv-Pol sur des domaines infinis. La topologie de convergence simple. Les graphes de Henson et autres exemples.

Jeudi 24/01. Introduction à la théorie de Ramsey. Fonctions canoniques. Classification de problèmes de Graph-SAT

Vendredi 25/01. Problèmes ouverts, projets de recherche.

Inscription

Inscription gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le 8 janvier en cliquant ici, remplissant le formulaire et envoyant le mail. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternatvement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à research.school.1@gmail.com, avec le sujet « Registration form — research school 3 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address:

wishes to attend the research school ‘Constraint satisfaction problems’, taking place at ENS Lyon, from Jan. 21 to Jan. 25.

ER01 (2012) : vérification et certification du logiciel

Intervenants : Patrick Cousot, Radu Iosif, Sandrine Blazy, Sébastien Bardin

Dates : 9 – 12 janvier 2012 – ENS Lyon

Programme (prévisionnel)

1- Interprétation abstraite : application à la vérification (P. Cousot)

  • Interprétation abstraite
  • Estimation de la précision de logiciels numériques
  • Vérification de systèmes complexes intégrés sur puce
  • Vérifications statiques sur des logiciels critiques embarqués temps-réel
  • Vérification de la sécurité de protocoles cryptographiques

2- Model-checking (R. Iosif)

  • Classical first- and second-order logic, finite word and tree automata, closure properties and language emptiness.
  • Relationship between Weak Monadic Second-Order Logic and finite automata. Infinite automata on words (Buechi, Mueller) and on trees (Rabin) automata, and their relationship with Monadic Second-Order Logic.
  • LTL Model Checking and applications

3- Certified compilation (S. Blazy)

  • Formally verified compiler
  • Software proof codesign
  • Translation validation
  • Proof carrying code

4- Test (S. Bardin)

  • Couverture structurelle et mutations
  • Tests de régression
  • Exécution dynamique symbolique
  • Bounded model-checking

Correspondant local : Ch. Alias
Page web de l’école

ER02 (2012) : Compressive Sensing

 

Justin Romberg
http://users.ece.gatech.edu/justin/Justin_Romberg.html
School of Electrical and Computer Engineering, Georgia Tech

VENUE

ENS Lyon, Site Jacques Monod.
Room: Amphitheater B – 3rd floor

(local correspondant: Paulo Gonçalves)

PROGRAM and MATERIAL

Basis decompositions and frames (3-4 hours)
[notation, basis, frames, dct-notes, wavelets, sparsity-overview]

  • fundamentals of basis and frame decompositions
  • the discrete cosine transform and applications to image/video compression
  • the lapped orthogonal transform
  • wavelets
  • thresholding for noise reduction

Sparsest decomposition from a dictionary (3-4 hours)
[lecture-2-1-sparseapprox, lecture-2-2-bp, lecture-2-3-upsparse]

  • omp and basis pursuit for selecting atoms
  • uncertainty principles and sparsest decomposition
  • the « spikes+sines » dictionary
  • general unions of orthobases

Introduction to compressive sampling and applications (2 hours)
[csoverview-part1,csoverview-part2,csoverview-part3,csoverview-part4

Recovering sparse vectors from linear measurements (6 hours/ 1 day)
[lecture-3-1-invprobs,lecture-3-2-ls,lecture-3-3-l1dual,lecture-3-4-l1cone,lecture-3-5-stable]

  • review of classical least-squares theory:
  • the svd, pseudo-inverse, stability analysis, regularization
  • sparse recovery conditions: l1 duality
  • sparsest decomposition revisited (with random support)
  • the restricted isometry property and sparse recovery
  • l1 for perfect recovery from noise-free measurements
  • l1 stability
  • l2 stability

Random matrices are restricted isometries (2 hours)
[lecture-4-1-gaussrip

Optimization (6 hours / 1 day)
[lecture-5-1-sdcg,lecture-5-2-newtonlog,lecture-5-3-streamingl2,lecture-5-4-streamingl1,lasso-dual-notes]
[siamOptimTalk

  • conjugate gradients
  • newton iterations
  • newton iterations
  • log-barrier methods
  • first-order l1 solvers
  • greedy algorithms and iterative thresholding
  • recursive least-squares
  • the Kalman filter
  • dynamic l1 updating

Low-rank recovery (2 hours)

TIMETABLE

Monday 9:  10:00am – 12:00am ; 2:00pm – 5:00pm  (5 hours)
Tuesday 10:  9:30am – 12:00am ;  2:00pm – 5:00pm  (5,5 hours)
Wednesday 11:  9:30am – 12:00am ; 2:00pm – 5:00pm  (5,5 hours)
Thursday 12:  9:30am – 12:30pm ; free afternoon  (3 hours)
Friday 13:  9:00am – 12:00am ; 2:00pm – 4:00pm  (5 hours)


ER03 (2012) : Calculabilité sur les entiers et les réels : de l’œuvre de Turing à la recherche actuelle

Intervenants : Laurent Bienvenu, Alexander Shen

En cette année 2012, qui célèbre les 100 ans après la naissance d’Alan Turing, nous présenterons les bases de la théorie qu’il a contribué à fonder, celle de la calculabilité. Nous rappellerons les concepts de base (machines de Turing, fonctions calculables) pour arriver rapidement à présenter quelques résultats et techniques fondamentaux de la calculabilité.

Le programme (prévisionnel) du cours est le suivant.

  1. Rappels de concepts de base
    • Machines de Turing
    • Ensembles et fonctions calculables, ensembles récursivement énumérables
  2. Indécidabilité
    • Problème de l’arrêt. Indécidabilité, et many-one complétude
    • Autres exemples de problèmes indécidables équivalents à l’arrêt:
      équations diophantiennes, problème du mot dans les semi-groupes,
      logique du premier ordre, etc.
  3. Oracles et réductions
    • Machines de Turing à oracle
    • Réduction Turing, degrés de Turing
  4. Hiérarchie arithmétique
    • Le jump comme opérateur sur les degrés.
    • Lemme de Schoenfield
    • La hiérarchie arithmétique et ses liens avec l’opérateur de jump
    • Complétude des ensembles \Sigma^0_n et \Pi^0_n, exemples de problèmes complets
  5. Résultats avancés sur les degrés
    • Existence de degrés non comparables (2 preuves: par diagonalisation et probabiliste par le théorème de Sacks)
    • Existence de deux degrés r.e. par la méthode de priorité de Friedberg-Muchnik
    • Existence d’un degré de Turing minimal
    • (Plus si le temps le permet: degrés « low », « high » et leur existence)
  6. Calculabilité sur les réels
    • Définition des fonctions calculables sur les réels et leurs propriétés élémentaires
    • Analyse calculable: théorèmes effectifs et non-effectifs

Les exposés seront donnés en anglais.

Dates : 16 au 20/01/2011

Planning:

– Lundi: 10h30-12h cours/TD; 14h-16h30 cours/TD
– Mardi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Mercredi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Jeudi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Vendredi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD

Examen vendredi jusqu’à 18h3o (à confirmer)

Correspondante locale : Natacha Portier

ER04 (2012) : programmation linéaire et combinatoire

Intervenants : Frédéric Giroire, Frédéric Havet et Nicolas Nisse

Dates : du 23 au 27 janvier 2012, à ENS Lyon, amphi B (sauf la séance de TP en E001)

Programme

Lundi
9h00 – 11h30
13h30 – 15h00
15h30 – 17h30
Introduction, Modelisation de problemes en PL, Simplexe approche geometrique.

Mardi
9h00 – 11h30 Dualité I
14h00 – 15h30 Dualité II
16h00 – 17h30 Ellipsoïde.

Mercredi
9h00 – 11h30 TP
13h30 – 15h00 Relaxation fractionnaire: Totale unimodularite.
15h30 – 17h30 Relaxation Lagrangienne.

Jeudi
9h – 11h30 Relaxation fractionnaire: Arrondis deterministes et aleatoires, integral gap.

Vendredi
9h – 11h30 Algorithmes primal-dual.
13h30 – 15h00 Examen.

Correspondant local : Nicolas Trotignon

Magnifiques notes de cours :
Introduction to linear programming duality
Ellipsoid method
Fractional relaxation
Lagrangian relaxation