ER02 : Compressive Sensing

Lecturer : Justin Romberg (Georgia Institute of Technology, Atlanta)

Outline of the school :
“The dogma of signal processing maintains that a signal must be sampled at a rate at least twice its highest frequency in order to be represented without error. However, in practice, we often compress the data soon after sensing, trading off signal representation complexity (bits) for some error (consider JPEG image compression in digital cameras, for example). Clearly, this is wasteful of valuable sensing resources. Over the past few years, a new theory of “compressive sensing” has begun to emerge, in which the signal is sampled (and simultaneously compressed) at a greatly reduced rate.
Compressive sensing is also referred to in the literature by the terms: compressed sensing, compressive sampling, and sketching/heavy-hitters.” [by courtesy of: http://dsp.rice.edu/cs]

  • Basis decompositions and frames (3-4 hours)
    •  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)
      •    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)
  • Recovering sparse vectors from linear measurements (6 hours/ 1 day)
    •    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)
  • Optimization (6 hours / 1 day)
    • conjugate gradients
    •   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)

Dates : 9-13/01/2012

Correspondant local : Paulo Goncalves

ER 01 : Stochastic Geometry for Wireless Networks

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

ER 03: Vision and Machine-learning

From the 24th to the 28th of January 2011 — ENS Lyon

The lectures will be delivered in English.

Goals

Some of the notable recent successes in automated visual recognition are results of combining advanced visual representations together with powerful machine learning techniques. The objective of this winter school is to provide an overview of basic tools and some latest advances in visual recognition together with the related machine learning algorithms. A particular emphasis will be given on topics related to recognition of objects and human actions in video and still images. Lectures will be given by experts in visual recognition and machine learning. Lectures will be complemented by practical sessions, where participants will obtain hands-on experience with the discussed material.

Speakers :

  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)

Tentative outline and schedule of the course

[L] means a lecture, and [E] means an exercise session.

If possible, please bring a laptop with you for the exercise sessions.

  • Monday, January 24
    • [L] 8:15 AM – 9:15 AM. Unsupervised learning (Zaid Harchaoui). Slides available here, here and here.
  • [L] 9:30 AM – 10:30 AM. Unsupervised learning (Zaid Harchaoui)
  • [E] 10:45 AM – 11:45 AM. Unsupervised learning (Zaid Harchaoui)
  • [L] 1:30 PM – 2:30 PM. Image features (Cordelia Schmid). Slides available here and here (ppt files) or here and here (pdf files).
  • [L] 2:45 PM – 3:45 PM. Image features (Cordelia Schmid)
  • [E] 4:00 PM – 5:00 PM. Image features (Cordelia Schmid, Josef Sivic)
  • Tuesday, January 25
    • [L] 8:15 AM – 9:15 AM. Camera geometry and Image Alignment (Josef Sivic). Slides available here.
    • [L] 9:30 AM – 10:30 AM. Camera geometry and Image Alignment (Josef Sivic)
    • [E] 10:45 AM – 11:45 AM. Camera geometry and Image Alignment (Ivan Laptev and Josef Sivic).
    • [L] 1:30 PM – 3:00 PM. Efficient visual search (Josef Sivic). Slides available here.
    • [L] 3:15 PM – 4:45 PM. Efficient visual search (Cordelia Schmid). Slides available here (ppt file) and here (pdf file).
  • Wednesday, January 26
    • [L] 8:15 AM – 9:15 AM. Bag-of-features models for category-level classification (Cordelia Schmid). Slides available here (ppt file) and here (pdf file).
    • [L] 9:30 AM – 10:30 AM. Bag-of-features models for category-level
      classification (Cordelia Schmid)
    • [E] 10:45 AM – 11:45 AM. Bag-of-features models for category-level classification (Ivan Laptev, Cordelia Schmid and Josef Sivic)
    • [L] 1:30 PM – 2:30 PM. Category-level localization (Ivan Laptev). Slides available here.
    • [L] 2:45 PM – 3:45 PM. Category-level localization (Ivan Laptev)
    • [E] 4:00 PM – 5:00 PM. Category-level localization (Ivan Laptev and Josef Sivic)
  • Thursday, January 27
    • [L] 8:15 AM – 9:15 AM. Motion and human actions (Ivan Laptev). Slides available here.
    • [L] 9:30 AM – 10:30 AM. Motion and human actions (Ivan Laptev)
    • [L] 10:45 AM – 11:45 AM. Motion and human actions (Ivan Laptev)
  • Friday, January 28
    • [L] 8:15 AM – 9:15 AM. Supervised learning (Zaid Harchaoui)
    • [L] 9:30 AM – 10:30 AM. Supervised learning (Zaid Harchaoui)
    • [E] 10:45 AM – 11:45 AM. Supervised learning (Zaid Harchaoui)

Total hours: 18 hours of lectures + 6 hours of practical exercises.

Prerequisites

The course is self-contained.

Bibliography

  • D.A. Forsyth and J. Ponce, “Computer Vision: A Modern Approach, Prentice-Hall, 2003.
  • J. Ponce, M. Hebert, C. Schmid, and A. Zisserman, “Toward category-level object recognition”, Springer LNCS, 2007.
  • R. Szeliski, “Computer Vision: Algorithms and Applications”, Springer, 2010.
  • O. Faugeras, Q.T. Luong, and T. Papadopoulo, “Geometry of Multiple Images,” MIT Press, 2001.
  • R. Hartley and A. Zisserman, “Multiple View Geometry in Computer Vision”, Cambridge University Press, 2004.
  • J. Koenderink, “Solid Shape”, MIT Press, 1990.

Registration

There are no registration fees. For organization reasons it is however necessary to register online; see the registration page.

Location and schedule

All the lectures will take place in “amphithéatre B”, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon, a.k.a. Campus Jacques Monod).

Local organizers

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

ER 04 (2011) : Separation logics and applications

Separation logic is an extension of Floyd-Hoare logic that makes it possible to reason about programs manipulating pointers. Since its introduction at the beginning of this millenary, it has led to several developments, which include tools for the automatic verification of properties of pointer manipulating programs, as well as reasoning about concurrent programs in a shared memory scenario.

This research school will take place in the week Jan.31st-Feb. 4, 2011.

Courses will be taught in english.

Slides:

HYang, intro, sep-logic, hiding, automation

AGotsman, concurrency, csl, lockfree, scheduler

MParkinson,abstract predicates, rely-guarantee, RGSep, deny-guarantee

Code: reverse.c, create.c, dispose.c, push.c, pop.c

The lecture notes on Separation Logic, written by J. Reynolds and mentioned by H. Yang in his lecture, are available here.

The prerequisite to follow the course is a basic knowledge of first-order logic.

Tool exercises: we suggest that attendees bring a laptop for the sessions devoted to tool exercises. Exercises will be made using the Verifast Program Verifier (follow the link to download and install the tool on your computer).

Lecturers

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

Topics (tentative description)

1) Basic separation logic.

  • [a] Basic proof rules and semantics of separation logic.
  • [b] Basic automatic verification algorithms based on separation logic.

2) Logic-based approaches on information hiding and data abstraction.

  • [a] Higher-order frame rules and abstract predicates.
  • [b] Automatic verification algorithm with abstract predicates.

3) Invariant-based approaches on the verification of concurrent programs.

  • [a] Concurrent separation logic.
  • [b] Automatic verification algorithm based on concurrent separation logic.

4) Rely-Guarantee.

  • [a] RGSep: the marriage of rely-guarantee and separation logic.
  • [b] Automatic verification with RGSep.
  • [c] Reasoning about liveness properties.
  • [d] Deny Guarantee.

Tentative schedule for the week. [L] means a lecture, and [E] means an exercise session.

Mon (5 hours)

  • [L] Introduction and basic semantics (HY)     10h30
  • [E] Introduction and basic semantics (HY)
  • [E] Concurrent programming (AG)      14h00
  • [L] Basic separation logic (HY)
  • [E] Basic separation logic (HY)

Tue (5 hours)

  • [L] Abstract predicate (MP)     9h00
  • [E] Abstract predicate (MP)
  • [E] Tool exercise 1 (AG)
  • [L] Information hiding (HY)   14h00
  • [E] Information hiding (HY)

Wed (7 hours)

  • [L] Concurrent separation logic (AG)     9h00
  • [E] Concurrent separation logic (AG)
  • [E] Tool exercise 2 (AG)
  • [L] RGSep (MP)              13h30
  • [E] RGSep (MP)
  • [L] Automation (HY)     16h00
  • [E] Automation (HY)

Thu (4 hours)

  • [L] Soundness of concurrent separation logic (AG)        9h00
  • [L] Deny/Guarantee (MP)
  • [E] Deny/Guarantee (MP)
  • [L] ..

Fri (3+1 hours)

  • [L] Liveness (AG)          9h00
  • [E] Liveness (AG)
  • [L] Concurrent abstract predicate (MP)
  • Exam     (end: 13h00)

Please contact Daniel Hirschkoff if you have any question regarding this course.

ER 05 (2011) : Complexité algébrique, complexité de comptage et applications en physique statistique

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

Ce cours sera donné en Français.

ER 06 : Rule-based modeling and application to biomolecular networks

From 2011 Feb the 14th to Feb. the 18th — ENS Lyon

Links to main documents

Goal

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.

Speakers

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

Pedagogical materials will be in English.

Lectures will be given in English.

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.

Software

Preliminary requirements

This course requires no prelimary knowledge.

The fundamental notions which will be used in this course will be properly introduced.

Bibliography

Local organizer

Olivier Laurent

ER-01 : Algorithms for geometric approximation

From the 11th to the 15th of January 2010 — ENS Lyon

Goals

More and more fields like biology, statistical analysis or machine learning, have to deal with data which are actually scatter plots in high dimensional spaces. These data have some topological and geometrical characteristics that express the properties of the modelled systems. For instance, the density of a scatter plot may be concentrated around a variety of intrinsic dimension much lesser that the one of the ambient space. Extracting such an information is not an easy task. First, the data suffer from some noise. Then, the structures and the algorithms of algorithmic geometry often have complexities that increase exponentially with the dimension and are not well scalable for this kind of data.

This series of lectures proposes an introduction to algorithmic geometry, focused on the approximation and geometrical object sampling issues. It starts from classical concepts (convex hull, Voronoi diagrams) and addresses recently developed methods (core sets, topological persistence) in order to approximate the geometrical and topological properties of higher dimension objects, while avoiding the exponential explosion of complexity related to the dimension.

Lecturers

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

Outline of the course

Algorithms for geometric approximation

  1. Metric structures for point sets
    • Convex hulls, Voronoi diagrams and Delaunay triangulations (J.-D. Boissonnat)
    • Dimension reduction, approximate nearest neighbor search, the k-means algorithm (F. Chazal)
    • Randomized algorithms and core sets (M. Yvinec)
  2. Simplicial approximation of manifolds
    • Mesh generation by Delaunay refinement (M. Yvinec)
    • Restricted Delaunay triangulation, e-samples and surface mesh generation (J.-D. Boissonnat)
    • Manifold reconstruction in 3 and higher dimensions (J.-D. Boissonnat)
  3. Geometric inference (F. Chazal)
    • Sampling theory for compact sets
    • Persistent homology and data analysis

Prerequisite

The course is self-contained.

Bibliography

  • 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.

Registration

There are no registration fees. For organization reasons it is however necessary to register online; [registration closed].

Location and schedule

All the lectures will take place in “amphithéatre B”, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).
A tentative schedule:

  • Monday, January 11
    • 2:00 PM – 5:00 PM. Convex hulls, Voronoi diagrams and Delaunay triangulations (J.-D. Boissonnat).
      Slides available here then here.
  • Tuesday, January 12
    • 8:30 AM – 11:30 AM. Mesh generation by Delaunay refinement (M. Yvinec).
      Slides available here then here.
    • 1:30 PM – 4:30 PM. Restricted Delaunay triangulation, e-samples and surface mesh generation (J.-D. Boissonnat).
      Slides available here.
  • Wednesday, January 13
    • 8:30 AM – 11:30 AM. Dimension reduction, approximate nearest neighbor search, the k-means algorithm (F. Chazal).
      Slides available here.
    • 1:30 PM – 4:30 PM. Randomized algorithms and core sets (M. Yvinec).
      Slides available here then here.
  • Thursday, January 14
    • 8:30 AM – 11:30 AM. Sampling theory for compact sets (F. Chazal).
      Slides available here.
  • Friday, January 15
    • 8:30 AM – 11:30 AM. Manifold reconstruction in 3 and higher dimensions (J.-D. Boissonnat).
      Slides available here.
    • 1:00 PM – 4:00 PM. Persistent homology and data analysis (F. Chazal).
      Slides available here.

Local organizers

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

ER-02 : Graphs and Combinatorial Optimization

du 18 au 22 janvier 2010 — ENS Lyon

Intervenants :

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)

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)

ER-03: Game theory for networks

du 25 au 29 janvier 2010 — ENS Lyon

Intervenants :

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

ER-04 : New computation paradigms: physics-like models of computation, efficient algorithmics

From the 1st till the 5th february  2010 — ENS Lyon

Intervenants :


Schedule: (Amphi B of ENS-Lyon)

  • First part: Mon. 14:00-18:00, Tue. 14:00-18:00, Wed. 9:00-13:00.
  • Second part: Wed. 14:00-17:00, Thu. 9:00-12:00 & 14:00-17:00, Fri. 9:00-12:00.

Course outline :

Our understanding of what a computer is (models of computation)  and of the way one
 may use  it in  order to solve mathematical problems(algorithmics) is under
 constant evolution. Beyond  the traditional approach, which is essentially based
 upon deterministic discrete systems (automata  of all sorts), a new vision is
 emerging which considers that probabilistic phenomena (randomness, approximations)
 and even quantum phenomena (interference, entanglement) should not be seen as just
 added difficulties, but rather as novel tools awaiting to be exploited and offering
 remarkable  perspectives. What are the limits of the traditional approach which we
 can overcome with these new tools? What more can we expect from them?
Lecture 1 (P.Arrighi) : Quantum information, causality and cellular automata
Lately quantum physical phenomena turned out to be extremely useful for speeding up
 or securing a number of important information processing and communication tasks.
 In the last 15 years, rather impressive theoretical results show that qualitative
 and quantitative performances would then become possible, beyond reach of classical
 computation. For instance it was proved that a quantum computer can factorise an
integer number in polynomial time, or search for an element within a unstructured
list of n elements, in time square root of n. These results are a threat to contemporary
 cryptography, but what quantum physics takes on the one hand, it gives it back on
the other. Some quantum communication systems, already available in industry, warrant
 provably unconditionnally secure communication channels.
This module provides background material from linear algebra, then from quantum
 mechanics. Then main results relating to the particular, non-local nature of quantum
 information are then given. The course is then oriented towads the quest for a model
 of computation which is quantum and distributed at the same time, and that takes into
 account several of the fundamental symmetries of physics (causality,
 translation-invariance). This will bring us to the study of themes such as causality
 in quantum mechanics, the definition of cellular automata in such a context, the
 nature of the interplay  between Physics and Computation.
Syllabus:
- Linear algebra
- Postulates of quantum theory
- Explorations on the nature of quantum information (Deutsch's algorithm,
No-distinguishing, No-cloning, Super-dense coding, Teleportation)
- Density matrices, quantum operators
- Entanglement (classification, non-local boxes)
- Causal operators and their structure
- Cellular Automata : three definitions and their equivalence
- Axiomatic definition of quantum cellular automata
- Structure theorems
- Universal quantum cellular automata

LECTURE 2 (F. Magniez) : Efficient algorithmics
This course aims at tackling those techniques which enable the construction of
 efficient  algorithms for  a variety of contexts. These techniques rely on
tools stemming from  probabilities and approximations. The contexts model the
 sort of constraints that we are placing upon the machine in terms of
resources (time, space, randomness, query, comunication) and data access
(unconstrained (random access), or sequential (streaming)).
The themes we will hence cover:
- Random walks: k-SAT, (s,t)-CONNECTIVITY in RL
- Expander graphs: derandomizaton, (s,t)-CONNECTIVITY in L
- Approximation algorithms (approximation on the output)
- Property testing (approximation on the input)
- PCP Theorem  (light version): application to inaproximability results
- Streaming algorithm
- One-way communication complexity: application to non existence of
 streaming algorithms

Correspondant local

  • Pablo Arrighi

ER-05 : Game semantics and linear logic

February, 8-12, 2010 — ENS Lyon

Lecturers :

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 1:

  • Dan Ghica. Game semantics of programming languages with applications. February 2010.
  • Dan Ghica, Andrzej Murawski. Angelic Semantics of Fine-Grained Concurrency. ( pdf ) Annals of Pure and Applied Logic, Volume 151, Issues 2-3, February 2008, Pages 89-114

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

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