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

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

Moodle Link

In the programs

  • Semester: Spring
  • Exam form: Written (summer session)
  • Subject examined: Integer optimisation
  • Courses: 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
  • Courses: 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
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional

Reference week

Related courses

Results from graphsearch.epfl.ch.