Invited Seminars Thematic month The five weeks |
## Lattice Algorithmics
## 1. DatesFrom February 1st to February 5th, 2010. ## 2. Description of the weekThe 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).
- 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).
- 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- AnneBroise-CharacteristicExponentsOfTheJacobiPerronAlgorithm-RelatedSlides.pdf ... 3,401,404 bytes ... 19 March 2010 à 16h21
- AntonioVera-IntegerFactorizationUsingLattices.pdf ... 551,647 bytes ... 05 February 2010 à 18h12
- BrigitteVallee-LatticeReductionAlgorithms-InSmallDimensionsEuclidGauss-DescriptionAndProbabilisticAnalysis.pdf ... 922,949 bytes ... 04 January 1980 à 05h13
- BrigitteVallee-ModellingTheLLLAlgorithmViaSandpiles.pdf ... 563,450 bytes ... 04 January 1980 à 05h13
- CongLing-LatticesInCommunications.ppt ... 701,440 bytes ... 04 January 1980 à 05h13
- DamienStehle-IntroductionToModernLatticeBasedCryptography.pdf ... 2,579,238 bytes ... 04 January 1980 à 05h13
- EvaCurry-AQuestionAboutNearJordanForms.pdf ... 231,388 bytes ... 04 January 1980 à 05h13
- GillesLachaud-ArithmeticConvexity-SailsAndKleinPolyhedra.pdf ... 504,066 bytes ... 04 February 2010 à 15h10
- GuillaumeHanrot-ASurveyOfEnumerationTechniques.pdf ... 932,644 bytes ... 02 February 2010 à 15h27
- LauraLuzzi-AugmentedLatticeReductionForMIMODecoding.pdf ... 360,178 bytes ... 04 January 1980 à 05h13
- NicolasChevallier-BestSimultaneousDiophantineApproximations-NotesInFrench.pdf ... 214,263 bytes ... 19 March 2010 à 16h18
- OlegKarpenkov-MultidimensionalContinuedFractionsAndConjugacyClassesOfSLnZ.pdf ... 1,049,895 bytes ... 04 January 1980 à 05h13
- XavierPujol-SieveAlgorithmsForTheShortestVectorProblem.pdf ... 1,079,497 bytes ... 04 January 1980 à 05h13
## 7. Some pictures of some blackboardshttp://iml.univ-mrs.fr/~cassaign/mi2010/photos/week1/ ## 8. ParticipantsSee the page Lattice Algorithmics Participants |

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