Integer optimisation
Summary
The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years.
Content
1. Integer Programming, Polyhedra and the integer hull
2. Complexity and approximation algorithms for classical combinatorial integer programming problems
3. Lattices, Minkowski's Theorem, The LLL algorithm
4. Breaking Knapsack Cryptosystems
5. Transference bounds
6. Integer Programming in fixed dimension
7. Voronoi cells and single exponential time algorithms for shortest and closest vector
Learning Prerequisites
Recommended courses
- Linear algebra 1+2
- Introduction to Algorithms or Discrete Optimization
Assessment methods
Written exam
Resources
Bibliography
- Thomas Rothvoss, Integer Optimization and Lattices
- Oded Regev, Lattices in Compter Science, Lecture Notes
Moodle Link
Dans les plans d'études
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Integer optimisation
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Integer optimisation
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Integer optimisation
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines