Fiches de cours

Integer optimisation

MATH-504

Enseignant(s) :

Eisenbrand Friedrich

Langue:

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

Dans les plans d'études

Semaine de référence

 LuMaMeJeVe
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     
En construction
 
      Cours
      Exercice, TP
      Projet, autre

légende

  • Semestre d'automne
  • Session d'hiver
  • Semestre de printemps
  • Session d'été
  • Cours en français
  • Cours en anglais
  • Cours en allemand