Instructor: Prof. Friedrich Eisenbrand
Summary:
The course aims to introduce the basic concepts and results of integer optimisation with special emphasis on algorithmic problems on lattices that have proven to be important in theoretical computer science and cryptography during the past 30 years.
Content:
- Lattices
- Minkowski’s Theorem
- The LLL algorithm
- Breaking Knapsack Cryptosystems
- Transference Bounds
- Integer Programming in Fixed Dimension
- Voronoi cells and single-exponential time algorithms for shortest and closest vector
- Polynomial time factorisation over Q[x]
Prerequisites:
Linear Algebra, Discrete Optimisation (or Introduction to Algorithms)
Organisation:
The lectures and the weekly exercise sessions will take place on zoom. The lectures will be recorded. Links to the recorded lectures and the weekly exercises will be posted on piazza.
Resources:
- Thomas Rothvoß, Integer Optimisation and Lattices
- Oded Regev, Lattices in Computer Science