CR-06 : Approximations : from symbolics to numerics, with applications.

The goal of this course is to describe recent progresses (last 5 years or so) in lattice-based cryptology. Using lattices allows one to build public-key primitives with asymptotic efficiency superior to other existing systems, while providing much more precise security guarantees.

Course outline

  • Euclidean lattices : definitions, properties, algorithmic problems, lattice basis reduction, approximate algorithms
  • Classical lattice-based crypto : GGH, NTRU.
  • Modern techniques : discrete gaussians, smoothing parameter, statistical distance, sampling
  • Algorithmic problems underlying the new cryptographic functions : SIS, LWE
  • Lattice-based cryptographic functions : Hash functions, digital signatures, encryption, Identity-Based Encryption, Homomorphic Encryption.

Web page for the course

Lecturers

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