Coursebooks

Integer optimisation

MATH-504

Lecturer(s) :

Eisenbrand Friedrich

Language:

English

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. Lattices
2. Minkowski’s Theorem
3. 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
8. Polynomial-time factorization in Q[x]

Learning Prerequisites

Recommended courses

Assessment methods

Written

Resources

Bibliography

  1. Thomas Rothvoss, Integer Optimization and Lattices
  2. Oded Regev, Lattices in Compter Science, Lecture Notes

In the programs

Reference week

 MoTuWeThFr
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     
Under construction
 
      Lecture
      Exercise, TP
      Project, other

legend

  • Autumn semester
  • Winter sessions
  • Spring semester
  • Summer sessions
  • Lecture in French
  • Lecture in English
  • Lecture in German