Integer optimisation

MATH-504 / 5 crédits

Enseignant:

Langue: Anglais

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

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
  • Type: optionnel
  • 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
  • Type: optionnel
  • 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
  • Type: optionnel

Semaine de référence

Cours connexes

Résultats de graphsearch.epfl.ch.