Catégorie : Archives

Intervenant : François Baccelli (http://www.di.ens.fr/~baccelli/)

The lecture will be taught in English.

Dates : 10 – 14 janvier 2011 – ENS Lyon

Planning:

lundi : 10h30 : 12h30 – 14h00 : 17h00
mardi : 10h00 : 12h00 – 14h00 : 17h00
mercredi : 10h00 : 12h00 – 14h00 : 17h00
jeudi : 10h00 : 12h00 – 14h00 : 17h00
vendredi : 10h00 : 12h00 – 14h00 : 16h00

Objectif: Introduction à la géométrie stochastique et application à la modélisation des communications dans les réseaux sans fil.

Programme (prévisionnel)

Part I – Classical Stochastic Geometry

1. Poisson Point Process
2. Marked Point Processes and Shot-Noise Fields
3. Boolean Model
4. Voronoi Tessellation

Part II – Signal-to-Interference Ratio Stochastic Geometry

5. Signal-to-Interference Ratio Cells
6. Interacting Signal-to-Interference Ratio Cells
7. Signal-to-Interference Ratio Coverage
8. Signal-to-Interference Ratio Connectivity

Part III – Medium Access Control

9. Spatial Aloha: the Bipole Model
10. Receiver Selection in Spatial Aloha
11. Carrier Sense Multiple Access
12. Code Division Multiple Access in Cellular Networks

Part IV – Multihop Routing in Mobile ad Hoc Networks

13. Optimal Routing
14. Greedy Routing
15. Time-Space Routing

Prérequis : Probabilités (à cet effet, les étudiants de M1 sont vivement invités à suivre le cours de L3 « Probabilités – Statistiques« )

Documents de support : monographie « Stochastic Geometry and Wireless Networks » (2009), by F. Baccelli and B. Blaszczyszyn (available on-line at http://www.di.ens.fr/~baccelli/)

Correspondant local : P. Gonçalves.
Sponsor : Pôle ResCom du GDR CNRS ASR

Intervenants :  Claude Lemaréchal (http://www.inrialpes.fr/bipop/people/lemarechal/) &  Jérôme Malick (http://www.inrialpes.fr/bipop/people/malick/)

Dates : 17 – 21 janvier 2011 – ENS Lyon

Planning (sujet à modifications):

Lundi (3h30) —  Introduction

• 10h30 – 12h — présentation du cours, objectifs
• 13h30 – 15h30 — introduction a l’optimisation, exemples

Mardi (5h15) — Optimisation classique

• 10h30 -12h  — principes algorithmiques
• 13h30 – 15h15 — méthodes classiques, méthodes pour la grande taille
• 15h30 – 17h30 — TP

Mercredi (5h) — Optimisation convexe non-différentiable

• 09h00 – 12h00  — non-différentiabilité naturelle, ou provoquée
• 13h30 – 15h30  — TD

Jeudi (5h15) — Théorie de l’optimisation convexe

• 10h30 – 12h   — analyse convexe
• 13h30 – 15h15  — théorie de la dualité
• 15h30 – 17h30  — TD

Vendredi (5h) — Algorithmique de l’optimisation non-différentiable

• 9h – 10h30 — algorithmes à oracle
• 10h30 – 12h  — algorithmes pour problèmes structurés
• 13h30 – 15h30  — fin + examen

Langue de la présentation : FRANCAIS.

Objectifs:

1. introduction a l’optimisation, applications sur des problèmes réels
2. algorithmique de l’optimisation convexe non-différentiable
3. relaxations convexes de problèmes combinatoires, décomposables ou non-convexes structurés

Programme prévisionnel : (enveloppe supérieure du programme)

———————
Partie 1 : Introduction à l’optimisation
– qu’est ce qu’un problème d’optimisation ? objectifs, classification
– exemples: moindres carrés, gestion de production, allocation
– principes mathématiques, rôle de la convexité
– principes algorithmiques: estimation + correction

———————
Partie 2 : Algorithmes d’optimisation différentiable

2.1 principes des méthodes classiques
– estimation : (quasi- Gauss-) Newton
– correction : recherche linéaire, région de confiance
– exemple : classification supervisée

2.2 méthodes pour la grande taille
– mémoire limitée, Newton tronqué
– exemples : prévision météo, maximisation d’entropie

———————
Partie 3 : Optimisation non-différentiable: théorie et applications

3.1 motivations:
– non-différentiabilité naturelle
– non-différentiabilité provoquée : relaxation, problèmes décomposables, optimisation combinatoire

3.2 éléments d’analyse convexe
– sous-différentiabilité
– conjugaison, dualité (Lagrange, Fenchel)
– analyse de sensibilité, interprétation économique

3.3 applications :
– optimisation de la production électrique
– optimisation des réseaux de communication
– optimisation de valeurs propres, application en théorie des graphes

———————
Partie 4 : Algorithmes d’optimisation convexe non-différentiable

4.1 Problèmes à oracle
– méthodes: sous-gradient, plans sécants, faisceaux
– récupération primale
– identification du second-ordre

4.2 Problèmes à non-différentiabilité structurée
– exploitation de la structure
– méthode de points intérieurs
– optimisation semidéfinie (SDP)
– relaxations SDP et applications (combinatoire, stats)

———————
Partie 5 : Deux applications de l’optimisation

4.1 Apprentissage
– contexte, rôle de l’optimisation, exemples
– applications des algorithmes, nouveaux enjeux numériques, optimisation « huge-scale »
– illustrations en vision par ordinateur, en bio-stats

4.2 Optimisation polynomiale
– optimisation globale, lien avec l’optimisation semidéfinie (SDP)
– approximations successives par SDP, preuve de fermeture
– illustrations en commande de systèmes, en certification de programmes

Correspondants locaux : T. Begin et P. Gonçalves.
Sponsor : Pôle ResCom du GDR CNRS ASR

Du 24 au 28 janvier 2011 — ENS Lyon

Les cours de cette école seront dispensés en anglais. Merci de consulter la version anglaise de cette page où vous trouverez de plus amples informations (descriptif du cours, emploi du temps, etc.).

Intervenants :

1. Zaid Harchaoui (INRIA, LEAR, INRIA Rhône-Alpes)
2. Ivan Laptev (INRIA, WILLOW, INRIA Rocquencourt)
3. Cordelia Schmid (INRIA, LEAR, INRIA Rhône-Alpes)
4. Josef Sivic (INRIA, WILLOW, INRIA Rocquencourt)

Correspondants locaux

• Nicolas Brisebarre
• Guillaume Hanrot
• Jean-Michel Muller

Un certain nombre d’informations utiles se trouve sur la page principale des écoles de recherche en informatique fondamentale de l’ENS Lyon.

Cette école de recherche se déroulera durant la semaine 31 janvier – 4 février 2011. Les cours de cette école seront dispensés en anglais.

Intervenants:

• Hongseok Yang (Lecturer, Queen Mary University of London, UK)
• Alexey Gotsman (Assistant Professor, IMDEA, Spain)
• Matthew Parkinson (Researcher, Microsoft Research, Cambridge, UK)

Voir la version anglaise de cette page pour un descriptif du cours, et des informations à jour (remarque importante: les cours seront dispensés en anglais).

Responsable local: Daniel Hirschkoff (LIP), avec l’aide bienveillante d’Etienne Lozes (LSV).

Dates :07-11/02

Horaires :

• Lundi : 9h-12h15 et 14h-17h15 (Arnaud)
• Mardi : 9h-12h15 (Jesper) et 14h-16h (Guillaume)
• Mercredi : 9h-12h15 (Jesper) et 14h-16h (Guillaume)
• Jeudi : 9h30-12h45 (Sylvain) – rien l’après-midi
• Vendredi : 9h30-12h45 (Sylvain) et 14h30-16h30 (Guillaume) + QCM 20min

Intervenants :

• Arnaud Durand (Equipe de logique mathématique, université Paris 7)
• Jesper Jacobsen (Laboratoire de Physique Théorique, ENS)
• Guillaume Malod (Equipe de logique mathématique, université Paris 7)
• Sylvain Perifel (LIAFA, université Paris 7)

Correspondant local : Pablo Arrighi

Programme :

Le cours s'articulera autour de deux questions centrales en complexité :

• Peut-on compter efficacement le nombre de solutions d’un problème ? (p. ex. combien d’affectations satisfont une formule booléenne ?)
• Combien d’additions et de multiplications sont nécessaires pour calculer un polynôme ? (p. ex. peut-on calculer le permanent en un nombre polynomial d’opérations ?)

Nous verrons les liens forts qui existent entre ces deux questions, et comment elles éclairent le 
reste de la théorie de la complexité booléenne en apportant la puissance d'outils algébriques.

Ces questions sont également importantes en physique statistique car les propriétés thermodynamiques 
d’un modèle statistique dérivent de la fonction de partition, qui est une somme pondérée sur 
un très grand nombre d’états microscopiques du système : le problème acquiert ainsi une nature 
combinatoire. Nous verrons donc l'approche des physiciens pour résoudre des problèmes réputés difficiles.

Plan prévisionnel :

1. Comptage booléen

- Classes de comptage : définitions, propriétés.
- Complétude du permanent pour la classe #P.
- Propriétés de clôture.
- Théorème de Toda : compter est plus puissant qu'une alternance bornée de
  quantificateurs.

2. Physique statistique

- Physique statistique : pavages de dimères, entropie, etc.
- Comptage des appariements dans un pavage de dimères : résolution complète.
- Comptage des polygones autoévitants : approche numérique.
- Autres exemples par les matrices de transfert, phénomènes critiques.

3. Calcul de polynômes

- Classes algébriques : modèle de Valiant, classes VP et VNP, propriétés de
  base, complétude du permanent pour VNP.
- Variantes (avec ou sans constantes, degré borné ou non) : équivalence des
  différentes questions "VP=VNP?".
- Bornes inférieures (Baur-Strassen, polynômes ad-hoc, modèles restreints).
- Liens avec la complexité booléenne : comptage, calcul en espace
  polylogarithmique, dérandomisation...

Du 14 au 18 février 2011 — ENS Lyon

Links to main documents

• http://www.moodle-cri.org/mod/forum/discuss.php?d=1682
• Monday morning slides
• Monday afternoon slides
• Tuesday slides
• Material by J. Feret
• Thursday afternoon slides

Objectifs

The goal of this course is to give an overview on rule-based modelling.

Rule-based approaches (as in our own Kappa, or BNGL, or many other
propositions allowing the consideration of « reaction classes ») offer
some means to capture combinatorial molecular interactions as we find
them in biological subcellular systems. This is trying to fill a need
that seems ever more pressing – as molecular biology uncovers more
amazing combinational structures. In so doing we get a more physically
realistic, less parameter-hungry, and more structured approach to the
modeling/programming of combinatorial molecular networks.

We will explain the approach through numerous motivating examples. We
will also reenact various methods commonly employed in the
verification and analysis of concurrent systems to support our
approach with analytic tools, such as: static analysis (qualitative
and quantitative) for reachability questions and for the reduction of
dynamical systems, causality analysis (including methods for the
compression of partial time traces), and more specific « termination »
methods using local energy functionals to guarantee thermodynamical
correctness.

The intended audience is students and staff in theoretical computer
science/concurrency theory, computational biologists with an interest
in modelling techniques, statistical physicists/applied mathematicians
with an interest in biomodelling.

Intervenants

1. Vincent Danos
2. Jérôme Feret
3. Jean Krivine
4. Gregory Batt
5. Jonathan Hayman

Le matériel pédagogique sera en anglais.

Les cours auront lieu en anglais.

Timetable

Monday 14th [Amphi B]

• 9h30: Welcome [Amphi B, 3rd floor]
• 10h00-12h00: Basics of modeling (V. Danos) [Amphi D, ground floor]
   
• 14h00-15h30: Basics of modeling (V. Danos) [Amphi B]
• 15h45-17h00: Basics of modeling (V. Danos) [Amphi B]

Tuesday 15th [Amphi B]

• 10h00-12h00: Introduction to kappa (J. Krivine)
   
• 14h00-15h30: Dynamics (J. Krivine)
• 15h45-17h00: Dynamics (J. Krivine)

Wednesday 16th [Amphi B]

• 10h00-12h00: Static analysis (J. Feret)
   
• 14h00-15h30: Model reduction (J. Feret)
• 15h45-17h00: Model reduction (J. Feret)

Thursday 17th [Amphi B]

• 10h00-12h00: Model reduction (J. Feret)
   
• 14h00-15h30: Modeling session: epigenetics (J. Krivine)
• 15h45-17h00: Modeling session: epigenetics (J. Krivine)

Friday 18th [Amphi B]

• 10h00-12h00: Energy and syntax (V. Danos)
   
• 13h15-14h00: evaluation for ENS students
   
• 14h00-15h30: Extensions (G. Batt)
• 15h45-17h00: Extensions (J. Hayman)

Content

Basics of modeling : Petri-Nets, mass action law, detection of equilibriums and steady states, thermodynamic limit (Kurz theorem).

Introduction to kappa : Notion of model in biology, syntax and operational semantics.

Dynamics : Gillespie’s algorithm, scalability issue, causality.

Static analysis : Qualitative analysis, reachability (completeness result), species enumeration algorithm.

Model reduction : Information flow, ODE semantics, stochastic semantics.

Energy and syntax : Information flow, ODE semantics, stochastic semantics.

Extensions : Compartments, agent variants,diffusion.

Logiciels

• complx et simplx
  (plusieurs versions Windows, Linux, Mac / 32/64 / avec tcl/tk, ou sans)
• octave avec le package odepkg
• gnuplot
• graphviz
• java

Pré-requis

Ce cours ne nécessite pas de connaissances préalables.

Les notions fondamentales utilisées seront toutes introduites pendant le cours.

Bibliographie

• V. Danos, C. Laneve. Formal Molecular Biology. In Theoretical Computer Science 325, 2004.
• V. Danos, J. Feret, W. Fontana, R. Harmer,& J. Krivine. Rule-based modelling of cellular signalling. Invited in International Conference on Concurrency Theory(CONCUR 2007), number 4703 in Lecture Notes in Computer Science. 2007, © Springer.
• J. Krivine, V. Danos, A. Benecke. Modelling epigenetic information maintenance: a Kappa tutorial Invited tutorial in Computer Aided Verification(CAV 2009), number 5643 in Lectures Notes in Computer Science. 2009, © Springer.
• V. Danos, J. Feret, W. Fontana,& J. Krivine. Scalable modelling of biological pathways. Invited in Asian Symposium on Programming Systems(APLAS 2007), number 4807 in Lecture Notes in Computer Science. 2007, © Springer.
• V. Danos, J. Feret, W. Fontana, R. Harmer,& Jean Krivine. Abstracting the differential semantics of rule-based models: exact and automated model reduction. Invited in Logic in Computer Science (LICS 2010). 2010, © IEEE Computer Society.
• V. Danos, N. Oury. Energy and Termination. In Developments in Computational Models 2010, Causality, Computation, and Physics (DCM 2010). 2010, © Electronic Proceedings in Theoretical Computer Science.

Correspondant local

Olivier Laurent

du 11 au 15 janvier 2010 — ENS Lyon

Objectifs

De plus en plus de domaines comme la biologie, l’analyse statistique ou l’apprentissage automatique, ont à traiter des données qui sont en fait des nuages de points dans des espaces de grandes dimensions. Ces données sont porteuses de caractéristiques topologiques et géométriques qui traduisent les propriétés des systèmes modélisés. Par exemple, la densité du nuage de points peut être concentrée autour d’une variété de dimension intrinsèque bien inférieure à celle de l’espace ambiant. Extraire une telle information n’est pas une tâche facile. Tout d’abord les données sont généralement bruitées, Ensuite, les structures et algorithmes de la géométrie algorithmique ont souvent des complexités exponentiellement croissantes en fonction de la dimension et passent mal à l’échelle pour ce type de données.

Ce cours propose une introduction à la géométrie algorithmique, axée sur les problématiques de l’approximation et de l’échantillonnage des objets géométriques. Il part de certains concepts classiques (enveloppe convexe, diagrammes de Voronoi) et aborde des méthodes récemment développées (core sets, persistance topologique) pour approcher les propriétés géométriques et topologiques des objets en dimensions supérieures, tout en évitant l’explosion exponentielle de la complexité, lié à la dimension.

Intervenants :

1. Jean-Daniel Boissonnat
2. Frédéric Chazal
3. Mariette Yvinec

Plan du cours

Algorithmes pour l’approximation géométrique

1. Structures métriques pour les ensembles de points
   • Enveloppes convexes, diagrammes de Voronoi et triangulations de Delaunay (J.-D. Boissonnat)
   • Réduction de dimension, recherche approchée de plus proches voisins, l’algorithme k-means (F. Chazal)
   • Algorithmes randomisés et core sets (M. Yvinec)
2. Approximation simpliciale de variétés
   • Génération de maillage par raffinement de Delaunay (M. Yvinec)
   • Triangulation de Delaunay restreinte, epsilon-échantillons et génération
     de maillage de surfaces (J.-D. Boissonnat)
   • Reconstruction de variétés en dimension 3 et en dimension supérieure (J.-D. Boissonnat)
3. Inférence géométrique (F. Chazal)
   • Théorie de l’échantillonnage des compacts
   • Homologie persistante et analyse de données

Prérequis

Le cours ne suppose pas de prérequis. Toutes les notions fondamentales de géométrie algorithmique utilisées dans le cours seront exposées au préalable.

Bibliographie

• M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
• J.-D. Boissonnat and M. Teillaud, editors. Effective Computational Geometry for Curves and Surfaces, Springer-Verlag, 2006.
• J.-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.
• F. Chazal, D. Cohen-Steiner, Geometric Inference, submitted as a chapter in a book entitled « Tesselations in the Sciences », November 2007.
• F. Chazal, D. Cohen-Steiner, A. Lieutier, A Sampling Theory for Compacts in Euclidean Space, Proceedings of the 22nd ACM Symposium on Computational Geometry 2006.
• E. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.
• K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
• A. Zomorodian, Topology for Computing, Cambridge Monographs on Applied and Computational Mathematics, cambridge University Press, 2005.

Inscription

Il n’y a pas de frais d’inscription. Pour des questions d’organisation, il est toutefois nécessaire de s’inscrire en ligne ; [inscription fermée].

Lieu des cours et emploi du temps

Tous les cours auront lieu dans l’amphithéatre B, au 3ème étage du bâtiment GN1 (bâtiment principal de la partie « sciences exactes » de l’ENS Lyon).

Un emploi du temps possible est le suivant:

• Lundi 11 janvier
  • 14h-17h. Enveloppes convexes, diagrammes de Voronoi et triangulations de Delaunay (J.-D. Boissonnat).
    Transparents disponibles ici puis ici.
• Mardi 12 janvier
  • 8h30 – 11h30. Génération de maillage par raffinement de Delaunay (M. Yvinec).
    Transparents disponibles ici puis ici.
  • 13h30 – 16h30. Triangulation de Delaunay restreinte, epsilon-échantillons et génération de maillage de surfaces (J.-D. Boissonnat).
    Transparents disponibles ici.
• Mercredi 13 janvier
  • 8h30 – 11h30. Réduction de dimension, recherche approchée de plus proches voisins, l’algorithme k-means (F. Chazal).
    Transparents disponibles ici.
  • 13h30 – 16h30. Algorithmes randomisés et core sets (M. Yvinec).
    Transparents disponibles ici puis ici.
• Jeudi 14 janvier
  • 8h30 – 11h30. Théorie de l’échantillonnage des ensembles compacts (F. Chazal).
    Transparents disponibles ici.
• Vendredi 15 janvier
  • 8h30 – 11h30. Reconstruction de variétés en dimension 3 et en dimension supérieure (J.-D. Boissonnat).
    Transparents disponibles ici.
  • 13h – 16h. Homologie persistante et analyse de données (F. Chazal).
    Transparents disponibles ici.

Correspondants locaux

• Nicolas Brisebarre
• Jean-Michel Muller

Un certain nombre d’informations utiles se trouve sur la page principale des écoles de recherche en informatique fondamentale de l’ENS Lyon.

du 18 au 22 janvier 2010 — ENS Lyon

Intervenants :

• L. Esperet (7h)
• F. Maffray (6h)
• M. Preissmann (5h)
• A. Sebo (6h)

Lieu des cours et emploi du temps

Tous les cours auront lieu dans l’amphithéatre B, au 3ème étage du bâtiment GN1 (bâtiment principal du site « Sciences » de l’ENS Lyon), ENS Lyon, 46 allée d’Italie, Lyon 7ème.

Lundi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-17h15)
Mardi : Louis Esperet (8h-10h) ; Andras Sebö (10h15-12h15)
Mercredi : Andras Sebö (8h-10h) ; Myriam Preissmann (10h15-12h15) ; Andras Sebö (14h-16h)
Jeudi : Myriam Preissmann (9h30-12h45)
Vendredi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-16h)

Louis Esperet (slides -> cours1, cours2,cours3)

Cours 1 (Lundi 14h-17h15) Coloration vs. coloration par listes

• méthodes inductives (Thomassen)
• déchargement

Cours 2 (Mardi 8h-10h) Graphes sans triangles et coloration

• constructions
• méthodes probabilistes (premier moment)

Cours 3 (Vendredi 14h-16h) Coloration fractionnaire, coloration d’hypergraphes

• méthodes algébriques (Borsuk-Ulam)
• méthodes probabilistes (Lemme Local de Lovasz)

Frédéric Maffray (fiche exercices -> télécharger Fiche)

Cours 1 (Lundi 9h30-12h45):

• Introduction du concept de graphes parfaits
• Graphes triangulés, décomposition par clique d’articulation, sommets simpliciaux, ordre d’élimination, algorithme MCS,
• utilisation de ces structures pour résoudre les problèmes d’optimisation (coloration, clique max, stable max).
• Représentation d’un triangulé comme graphe d’intersection de sous-arbres d’un arbre.
• Exemples de graphes triangulés: graphes d’intervalles, graphes « splits ».

Cours 2 (Vendredi 9h30-12h45):

• Relation entre nombre chromatique et orientation (Gallai-Roy)
• graphes de comparabilité, ensembles partiellement ordonnés,théorème de Dilworth.
• théorème de Lovasz (parfait = complémentaire de parfait)

Myriam Preissmann

Cours 1 (Mercredi 10h15-12h15) :

• Flot maximum
• Algorithme « Push-Relabel » et flots paramétriques.
• Calcul de l’arête-connectivité d’un graphe non orienté avec, et sans calcul de flot max.

Cours 2 (Jeudi 9h30-12h45) :

• Flot de coût minimum.
• Les k-flots non nuls.
• Théorème du 8-flot.

Andras Sebö (fiches d’exercices -> télécharger Fiche 1, Fiche 2)

Cours 1 Mardi (10h15-12h15)

• Quelques modèles d’optimisation combinatoire.
• Matroïdes, algorithme glouton et polytôpe associé.

Cours 2 (Mercredi 8h-10h)

• Algorithme de l’intersection de deux matroïdes.
• Applications.

Cours 3 (Mercredi 14h-16h)

• Algorithme de couplage de cardinalité maximum (Edmonds).
• Théorème de caractérisation lié (Tutte-Berge).
• Applications et généralisations.

S’il y a des questions sur les exercices de la fiche fournie ci-dessus, vous pourrez les poser après le premier cours.

Bibliographie : Schrijver: Combinatorial Optimization; Lovász, Plummer: MatchingTheory; Lovasz: Combinatorial Problems and Exercises,

Autres informations pratiques

Voir la page des Ecoles du Master d’Informatique.

Correspondant local

Eric Thierry (prenom.nom@ens-lyon.fr)

du 25 au 29 janvier 2010 — ENS Lyon

Intervenants :

• Eitan Altman
• Rachid ElAzouzi
• Corinne Touati

Location and schedule

All the lectures will take place in amphitheater B, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).

Schedule:

• Monday 25/01/2010 Morning: Eitan Altman 11:00 – 13
  Zero-sum Games: these are the most elementary game where there are two players, one playing against the other. These games are useful for modeling malicious users, denial of service attacks, jamming etc.  We introduce the notions of upper and lower values as well as the notion of value of a zero-sum game. We present some minimax theorems which are used to establish the existence of a value. We end with an LP solution for Zero sum matrix games. We present examples of games with and without a value.   Solution of 2 by 2 matrix games.
  Non-zero sum games. We present the notion of Nash equilibrium as   well as epsilon Nash equilibrium. We then introduce    Coordination Games and present their properties. We then study    Lemke’s algorithm for computing the equilibrium in non-zero sum games    with two players. We present examples of channel selection games.   We end this part with the concept of Correlated equilibrium

  Afternoon: Corinne Touati 14h30 – 17h00
  Notions from cooperative game theory: Bargaining and fairness.
  Le but de cette partie est de comprendre comment appréhender les qualités d’une allocation (équilibre de Nash ou valeur optimisant une fonction par exemple). Nous commençons par la définition de la propriété d’optimalité. Parmi l’ensemble des points optimaux, un ensemble de critères permet de choisir un point dit équitable. Nous présentons des techniques numériques permettant d’approcher la frontière de Pareto et de calculer les points équitables. Enfin, nous verrons dans une dernière partie des méthodes d’évaluations des performances d’allocations, en terme à la fois d’équité et d’optimalité.
  1. Optimalité
  a. Définition de Pareto et notions liées
  b. Propriétés des ensembles de Pareto (par ex. compacité)
  c. Epsilon-approximation et méthodes de résolutions
  d. Introduction à l’optimisation multi-critères, exemple d’un problème d’ordonnancement.

• Tuesday 26/01/10  Morning: Corinne Touati 10:30 – 12:30
  2. Fairness and Nash bargaining.
  a. Axiomatic definitions: Thomson, Raiffa-Kalai-Smorodinsky, Nash)
  b. Equivalent optimizations and properties
  c. Alpha fairness
  d. Algorithmic solutions.
  e. Application to flow control and TCP.
  3. Performance evaluation of the resource allocation:
  a. The Gain index,
  b. Price of anarchy
  c. Selfish Degradation Factor
  d. Pareto equilibrium

  Afternoon: Eitan Altman 14:00 – 16:30
  Convex games. These are games with a convex compact space. We shall study Rosen’s theory for the existence of an equilibria,   The strict diagonal concavity property (which extends concavity    to a game context). This notion is used to establish    uniqueness of equilibrium in convex games.
  We then introduce games with coupled constraints    as in Rosen, as well as the related    notion of generalized Equilibrium. These are equilibria in which the space of actions of each player are not independent: the actions available to a player may depend on those already chosen by others (for example, if there are capacity constraints over links then the amount of flow that a player can send over a link depends on how much other players send over that link). In the presence of such constrained there is in general no uniqueness of equilibrium. We thus introduce the problem of equilibrium selection. We introduce in particular the notion of normalized Nash equilibrium which and and relate it to scalable pricing.

• Wednesday 27/01/10Morning Rachid El-Azouzi 9h30 – 12h30
  Energy-efficient power control games Non-cooperative games where terminals want to maximize the number of information bits per joule are analyzed. The solution of this game is shown to be inefficient.
  Medium access games: the aloha game.

  Afternoon Rachid El-Azouzi 14:00 – 17:00
  Super-modular Games and Potential Games. These are two classes of games in which not only do we know that equilibria exists, but we also know that sequence of best responses of players convenrge to the equilibrium. In particular, we show how potential games can be transformed into a global optimization problem whose optimum corresponds to the equilibrium of the original game.
  Routing games Wardrop equilibrium: the players are modeled as infinitesimally small, which means that we have a continuum of players. computation of the equilibrium of the game
  Definitions. Price of anarchy, price of stability, variational inequalities. Link between Nash and Wardrop equilibria.

• Thursday 28/01/10Morning: Corinne Touati 10:30 – 12:30
  Evolutionary game theory and population games. (games are related to infinite number of players). We introduce the concept of equilibrium is Evolutionary Stable Strategy, which is more general than a Nash equilibrium in a given sense.
  Replicator Dynamics and evolutionary dynamics: Methods for convergence to equilibria, cases of non-convergence and oscillations. Based on the idea that higher fitness will be adopted by a growing number of individuals. Other evolutionary dynamics: Brown-von Neumann-Nash, Best response dynamics, Fictitious play, Logit response dynamics. We will discuss about the main difference of those dynamics and present a generalization which is called the revision protocols.

  Afternoon: Corinne Touati 14:00 – 17:00
  Learning in games. All the previous evolutionary dynamics are related to learning process. The theory of learning in games explains the dynamic behavior of each player or agents depending on its own experience. Those learning processes related to the evolutionary dynamics, are used in order to construct distributed algorithms converging to equilibrium (Nash or ESS). We will introduce an example of distributed algorithm proposed in the literature which has been widely used in the networking community for power control, pricing, resource sharing and routing protocol. We will present other reinforcement learning algorithms: the Erev-Roth algorithm, and the Arthur algorithm for a variant of the last one with renormalization. Those distributed algorithms have interesting properties of implementation as they are totally distributed but they suffer from stability problems at the boundary of the state space. We will investigate how feedback delays and errors affect convergence

• Friday 29/01/10Morning: Eitan Altman  11:00  – 13:00
  The Braess paradox. Routing games with finitely many users: Uniqueness of the equilibrium.  Parallel links. Load balancing problems. Relation to Ad-hoc networks.

  Afternoon: Eitan Altman 14:30 – 17:00
  Introduction to Repeated Games. Threats and punishments. Credibility of threats and refinements of equilibria. Stochastic games and Dynamic programming approach for stochastic games. The discouted cost and the average cost games. Product stochastic games. Anonymous sequential games, Markov Decision Evoluationary Games.

Correspondant local

• Paulo Goncalves

Du 1er au 5 février 2010 — ENS Lyon

Intervenants :

• Première partie: Pablo Arrighi, Julien Degorre
• Deuxième partie: Frédéric Magniez

Emploi du temps: (Salle Amphi B de l’ENS-Lyon)

• Première partie: Lun. 14:00-18:00, Mar. 14:00-18:00, Merc. 9:00-13:00.
• Deuxième partie: Merc. 14:00-17:00, Jeu. 9:00-12:00 & 14:00-17:00, Ven. 9:00-12:00.

Résumé du cours : 
Notre compréhension de ce qu'est un ordinateur (modèles de calculs) et de la manière
 dont il peut résoudre des problèmes mathématiques(algorithmique) est en évolution
 constante. Au-delà de l'approche traditionnelle, essentiellement fondée sur des
 systèmes déterministes et discrets (automates etc.) , une nouvelle vision émerge
 et qui se saisit des phénomènes probabilistes (aléatoire, approximation) et  même
 des phénomènes quantiques (interférence, enchevêtrement) en les concevant non plus
 comme des difficultés à surmonter, mais comme de nouveaux outils offrant des
perspectives remarquables. Quelles sont les limites de l'approche traditionnelle et
 qui sont franchies grâce à ces nouveaux outils? Jusqu'où peut-on éspèrer aller grâce
à eux?

Partie 1 (P.Arrighi, J.Degorre): Information quantique, causalité et automates cellulaires
La physique quantique a précisément mis en évidence des phénomènes extrêmement
 utiles pour représenter, traiter et communiquer l'information. Ceci a donné
 lieu dans les 15 dernières années à de splendides  résultats théoriques qui
 montrent que des performances quantitatives et qualitatives hors de portée de
 l'informatique classique deviennent alors possibles. Ainsi il est prouvé
qu'un ordinateur quantique  pourrait factoriser des nombres entiers en temps
 polynomial, ou bien rechercher un élément parmi une liste désordonnée de
 taille n en temps racine carrée de n.  Ces résultats menacent la
 cryptographie moderne; mais ce que la physique quantique prend d'une main
 elle le redonne de l'autre.  Ainsi des systèmes de transmission quantiques,
 déjà commercialisés, permettent d'obtenir une sécurité prouvée et
 inconditionnelle des communications. Ce cours effectuera d'abord tous les
 rappels nécessaires en algèbre linéaire. Les postulats de la mécanique
quantique seront introduits, puis les principaux concepts et résultats connus
 et ayant trait à la nature particulière et non-locale de l'information
 quantique.
Le cours sera alors axé vers la quête d'un modèle de calcul à la fois quantique et
 distribué, prenant en compte plusieurs des symmétries fondamentales de la physique
 (causalité, invariance par translation). C'est ce qui nous amènera à aborder des
 thèmes comme la causalité en mécanique quantique, les automates cellulaires dans
 un tel contexte, et la nature des relations entre physique et calcul.
Plan:
- Rappels d'algèbre linéaire
- Postulats de la théorie quantique
- Explorations sur la nature de l'information quantique (Algorithme de Deutsch,
Non-disctinction d'états non-orthogonaux, No-cloning, Codage Super-dense,
 Téléportation)
- Matrices de densité, opérateurs quantiques
- Enchevêtrement quantique (classification, boîtes non-locales)
- Opérateurs causaux et leur structure
- Automates cellulaires : trois définitions et leur équivalence
- définition axiomatique des automates cellulaires quantiques
- théorèmes de structure
- automates cellulaires quantiques universels
Partie 2 (F. Magniez): Algorithmique efficace
Le but du cours est d'aborder les techniques permettant d'élaborer des algorithmes
 efficaces  dans  plusieurs contextes. Les techniques reposent sur des outils
 probabilistes et d'approximation. Les contextes modélisent les contraintes
 exercées sur la machine concernant ses ressources (temps, espace,  aléa, requête,
 communication) et l'accès aux données (non contraint (random access) ou
séquentiel (streaming)).
Les domaines abordées seront donc :
- Marches aléatoires : k-SAT, (s,t)-CONNECTIVITY dans RL
- Graphes d'expansion (expander) : derandomizaton, (s,t)-CONNECTIVITY dans L
- Algorithmes d'approximation (approximation du résultat)
- Property testing (approximation sur l'entrée)
- Théorème PCP (version light) : application à des preuves de non approximation
- Streaming algorithms
- One-way communication complexity : application a des preuves de non
 existence de streaming  algorithms

Correspondant local
 Pablo Arrighi
			

February, 8-12, 2010 — ENS Lyon

Lecturers :

• Dan Ghica (University of Birmingham)
• Olivier Laurent (LIP, ENS Lyon)
• Lorenzo Tortora de Falco (University of Roma 3)

Introduction

Linear logic was introduced by Jean-Yves Girard in 1986 as a
refinement of intuitionnistic logic. In the context of the
Curry-Howard correspondence between proofs and programs, linear logic
has renewed a lot of questions in proof theory in relation with the
semantics of programs.

Partly inspired by models of linear logic, game semantics provided in
1994 the first fully abstract model of the functional programming
language PCF. It has evolved towards the interpretation of various
additional programming features as well as applications to the
verification of programs.

These topics have evolved in two separate directions (proof theory for
linear logic, and programming semantics for game semantics) but with
many transfers of ideas between them along the past fifteen years.

Location and schedule

The lectures will take place in “amphithéatre B”, at the 3rd floor of the GN1 building (main building at 46, allée d’Italie).
Tentative schedule:

• Monday, February 8:
  • 10:00 AM – 11:30 AM Game semantics
  • 1:30 PM – 4:30 PM Linear logic
• Tuesday , February 9:
  • 8:30 AM – 11:30 AM Game semantics
  • 1:30 PM – 4:30 PM Linear logic
• Wednesday, February 10:
  • 8:30 AM – 11:30 AM Game semantics
  • 1:30 PM – 4:30 PM Linear logic
• Thursday, February 11:
  • 9:30 AM – 12:30 AM Linear logic
• Friday, February 12:
  • 8:30 AM – 11:30 AM Game semantics
  • 1:30 PM – 3:00 PM Game semantics

On thursday, Febr. 11 afternoon, the
Choco seminar , on related topics, might also interest the participants.

Course outline

Course 1: Game Semantics with Applications [in English, 12h]

Dan Ghica (University of Birmingham)

content:

• basic concepts of game semantics
• the fully abstract game model of a procedural concurrent programming language
• concrete algorithmic representations of game models
• applications of finite-state game models to program verification
• approximating and refining game models
• a survey of more advanced techniques for program verification using game models
• Geometry of Synthesis, a categorical framework for circuit design
• extracting circuit descriptions from game semantics
• a survey of open problems in game semantics and applications

Course 2: Linear Logic [12h]

Lorenzo Tortora de Falco (University of Roma 3)
Olivier Laurent (LIP – ENS Lyon)
content:

• sequent calculus for linear logic (1h30, monday LTdF)
• proof-nets (3h, monday, tuesday LTdF)
• translations of intuitionistic and classical logics (3h, tuesday, wednesday OL)
• the coherent model and the relational model (1h30,wednesday LTdF)
• geometry of interaction and game semantics for linear logic (3h, thursday OL)

(LTdF: Lorenzo Tortora de Falco, OL: Olivier Laurent)

References and documents

Course 2:

• Olivier Laurent. Théorie de la démonstration. pdf .
  pages 89-90 (section 5.3), 87-89 (section 5.2), pages 143-150 (chap. 10), pages 111-122 (chap. 7), pages 130-134 (section 8.3)
• Samson. Abramsky. Semantics of Interaction: an introduction to Game Semantics. pdf pages 1-14.

Local contact

• Patrick Baillot

There are several useful informations on the main page of the research schools in Computer Science at ENS Lyon.

du  15 au 19 février 2010 — ENS Lyon

Plus d’informations sur: http://perso.ens-lyon.fr/florent.de.dinechin/beyond_the_pc.html

Intervenants :

• Accélérateurs matériels  pour la bioinformatique (Dominique Lavenier, 6 hours)
• High-Level Synthesis (Philippe Coussy, 6 hours)
• Introduction au test numérique (Michel Renovell, 4 hours)
• Optimizations for multicore and GP-GPU architectures (J. Ramanujam, 6 hours)
• Optimisation de la consommation (Yves Durand, 2 hours)

Correspondants locaux

• Christophe Alias
• Florent de Dinechin