Integer optimisation
MATH-504 / 5 credits
Teacher:
Language: English
Remark: pas donné en 2024-25
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
In the programs
- Semester: Spring
- Exam form: Written (summer session)
- Subject examined: Integer optimisation
- Lecture: 2 Hour(s) per week x 14 weeks
- Exercises: 2 Hour(s) per week x 14 weeks
- Type: optional
- Semester: Spring
- Exam form: Written (summer session)
- Subject examined: Integer optimisation
- Lecture: 2 Hour(s) per week x 14 weeks
- Exercises: 2 Hour(s) per week x 14 weeks
- Type: optional
- Semester: Spring
- Exam form: Written (summer session)
- Subject examined: Integer optimisation
- Lecture: 2 Hour(s) per week x 14 weeks
- Exercises: 2 Hour(s) per week x 14 weeks
- Type: optional
Reference week
Mo | Tu | We | Th | Fr | |
8-9 | |||||
9-10 | |||||
10-11 | |||||
11-12 | |||||
12-13 | |||||
13-14 | |||||
14-15 | |||||
15-16 | |||||
16-17 | |||||
17-18 | |||||
18-19 | |||||
19-20 | |||||
20-21 | |||||
21-22 |
Légendes:
Lecture
Exercise, TP
Project, labs, other