Math-Info 2010

Towards new interactions between mathematics and computer science

 

Invited Seminars

Thematic month

The five weeks

Lattice Algorithmics

1.  Dates

From February 1st to February 5th, 2010.

2.  Description of the week

The Gauss lattice reduction algorithm transforms in polynomial time any basis of a two-dimensional lattice into a minimal basis of this lattice. This procedure is central in the well-known Lenstra-Lenstra-Lovász (LLL) algorithm, that generalizes Gauss algorithm to higher dimensions, producing in polynomial time a LLL-reduced lattice basis (a basis whose vectors are short and nearly orthogonal). The LLL algorithm is widely used in many contexts (polynomial factorization, diophantine approximation, cryptography,...). However, its average (or smooth) complexity is badly understood. This week will focus on new results on lattice algorithmics.

Topics will include:

  • Complexity of lattice problems.
  • Average analysis of lattice reduction algorithms (in particular LLL).
  • Dynamics on the space of lattices.
  • Applications
    • Multidimensional diophantine approximation.
    • Cryptography.
    • Communications.
  • ...

This week will be organised in association with the ANR project Lareda.

3.  Confirmed morning lectures (each point is a course of 1h30, roughly in the following order)

  • Ali Akhavi:
    • Introduction to lattice reduction and to the LLL algorithm.
    • Analysis of the LLL algorithm in the uniform model of the unit ball.
  • Nicolas Chevallier
    • Best simultaneous diophantine approximations.
  • Damien Stehlé:
    • Cryptography and Euclidean lattices (2 courses).
Abstract: Lattice-based cryptography started in the mid 1990's, with the pioneering works of Ajtai on the Shortest Vector Problem, and with the novel GGH and NTRU cryptosystems. It has now become an extremely active branch of cryptography, thanks to a unique combination of attractive features. Lattice-based cryptographic primitives are often simple and elegant, they are very flexible and also possibly quite efficient. But above all, they provide unprecedented notions of security: breaking the primitive would provide efficient algorithms for worst-case instances of problems closely related to NP-hard problems. A popular security feature is its apparent resistance to quantum computers. In this course, we will survey the computational problems underlying lattice-based cryptography and describe a few recent schemes.
  • Brigitte Vallée:
    • Analysis of the LLL algorithm in two dimension.
    • Random model and sand pile model for the LLL algorithm.
  • Emmanuel Breuillard:
    • Invitation to the dynamics on the space of lattices (2 courses).
Abstract: This lectures will be devoted to an informal introduction to dynamics on the space of lattices. I will first describe some basic tools of this trade such as the Mahler compactness criterion, the Howe Moore property, the Mautner phenomenon. Then I will discuss Ratner's theorem and Margulis' proof of the Oppenheim conjecture.
  • Anne Broise:
    • Lyapunov exponents and the rate of convergence in the Jacobi-Perron Algorithm.

4.  Proposed afternoon workshops (add your suggestions here)

  • Yitwah Cheung will speak about successive minima of a lattice.
  • Cong Ling is proposing a working session about the application of lattices in communications.
  • Fréderic Paccault is interested in the modelization of lattice reduction algorithms as a dynamical system with holes.
  • Thierry Monteil is interested in filling the gap between th behavior LLL algorithm and the dynamics of the geodesic flow on homogeneous spaces.
  • Oleg Karpenkov will speak about Multidimensional continued fractions and conjugacy classes of SL(n,Z).
  • Antonio Vera proposes a talk on Schnorr's lattice-based integer factorization algorithm.
  • Dmitry Kleinbock will speak about an application of mixing on the space of lattices to Diophantine approximation.
  • Damien Stehlé is proposing a working session on how to solve the Shortest Lattice Vector Problem exactly.
  • Gilles Lachaud. Voiles de Klein
  • Anne Broise. Exposants de Lyapunov de l'algorithme de Jacobi Perron.

5.  Schedule

  • Monday 1st
    • 9h00-10h30 : Ali Akhavi - Basic properties of lattices.
    • 11h00-12h30 : Ali Akhavi - The LLL algorithm.
    • 15h00-16h00 : Cong Ling - Lattices in communication.
    • 16h00-17h00 : Laura Luzzi - Augmented Lattice Reduction for MIMO decoding.
    • 17h00-18h30 : Damien Stehlé - Cryptography and Euclidean lattices I.
  • Tuesday 2th
    • 9h00-10h30 : Nicolas Chevallier - Best simultaneous diophantine approximations.
    • 11h00-12h30 : Damien Stehlé - Cryptography and Euclidean lattices II.
    • 15h30-16h00 : Eva Curry - A question about "near-Jordan" forms.
    • 16h00-17h00 : Guillaume Hanrot - A survey of enumeration techniques.
    • 17h30-18h00 : Xavier Pujol - Sieve algorithms for the Shortest Vector Problem.
    • 18h00-19h30 : Apéritif at IML.
  • Wednesday 3th
    • 9h00-11h00 : Brigitte Vallée - Lattice Reduction Algorithms: in small dimensions : EUCLID, GAUSS, Description and Probabilistic Analysis.
    • 11h30-12h30 : Emmanuel Breuillard - Invitation to the dynamics on the space of lattices I.
    • 17h00-18h00 : Antonio Vera - Integer Factorization using lattices.
    • 18h15-19h30 : Yitwah Cheung - Sequence of best approximants in higher dimensions.
  • Thursday 4th
    • 9h00-10h00 : Emmanuel Breuillard - Invitation to the dynamics on the space of lattices II.
    • 10h15-11h15 : Emmanuel Breuillard - Invitation to the dynamics on the space of lattices III.
    • 11h30-12h30 : Brigitte Vallée - Modelling the LLL Algorithm via Sandpiles.
    • 14h30-15h30 : Dmitry Kleinbock - Application of mixing on the space of lattices to Diophantine approximation.
    • 15h30-16h30 : Gilles Lachaud - Arithmetic Convexity, Sails and Klein Polyhedra.
    • 17h00-18h00 : Oleg Karpenkov - Multidimensional continued fractions and conjugacy classes of SL(n,Z).
    • 18h00-19h00 : Mariya Georgieva - Computer experiments for the sandpile model.
  • Friday 5th
    • 9h00-10h30 : Anne Broise - Description of the Jacobi-Perron Algorithm.
    • 11h00-12h30 : Anne Broise - Lyapunov exponents and the rate of convergence in the Jacobi-Perron Algorithm.

6.  Currently uploaded slides

7.  Some pictures of some blackboards

http://iml.univ-mrs.fr/~cassaign/mi2010/photos/week1/

8.  Participants

See the page Lattice Algorithmics Participants

 

For any technical question or comment regarding this wiki, you can contact the wemaster.