Lecturer
News
February 25: Room for exercise sessions updated.
Objectives
This is a 4-credits doctoral course in mathematics and computer science. The goal of the course is mainly to learn some of the state-of-the-art results and open problems in the algorithmic geometry of number and integer programming. Starting from the fundamentals of (point) lattice theory, we shall the switch to some of the main “milestones” of the research on integer points in polyhedra, to which we attribute the Khintchine’s flatness theorem, the LLL-algorithm and the Barvinok’s counting algorithm.
Description
Integer points in polyhedra, or more generally, lattice points in convex sets form an interesting research topic from at least two different perspectives. The traditional geometry of numbers, initiated by H. Minkowski, mostly concentrates on the conditions, under which a given convex set contains a lattice point. Another interesting direction is algorithmic, where the goal is to find a lattice point in a convex set if one exists. Particularly, if the set is a polyhedron, i.e., the intersection of finitely many half-spaces, the problem is known as an integer linear programming problem. While being NP-complete in general, this problem can be solved in polynomial time if the dimension is fixed (i.e., not counted as a part of the input). This celebrated result of H. Lenstra expoloited the tools from the geometry of numbers and stimulated a deep research on the algorithms in this field. Recently, Barvinok proposed an algorithm for counting integer points in a polyhedron, exploting some different techniques—namely, encoding all integer points in a polyhedron via a short rational generating function.
Topics
Lattices, Blichfeldt’s and Minkowski’s theorems
Lattice basis reduction, LLL-algorithm
Applications of LLL-algorithm (integer programming, Diophantine approximation)
Integer hull of a polyhedron in fixed dimension
Rational generating functions and Barvinok’s counting algorithm
Integer points in parametric polyhedra (if time permits)
Grading
Oral exam (+ bonus points from exercise sessions)
Schedule
Lectures: Tuesday 14:15-16:00, MA 10
(First Lecture: February 17, 2009)
Exercise sessions: Thursday 16:15-18:00, MA B1 524 (TTX)
(First Exercise session: February 19, 2009)
Final exam: TBA
Notes
Lecture notes of D. Micciancio
The following lecture notes intend to incorporate both what we covered on the lectures and what we discussed during the exercise sessions.
Course description (preliminary)
Algorithms and complexity (preliminary)
Some basic algorithms (preliminary)
Lattices (February 17)
Hermite normal form and its applications (February 24)
Equivalent definition of lattices and Minkowski’s theorem (March 3)
Generalized Gauss reduction algorithm (March 10)
LLL algorithm (March 17)
Basics of linear programming and integer programming in fixed dimension (March 24)
Introduction to counting, valuations (March 31)
Identities in the algebra of polyhedra (April 7)
no lecture (April 14)
Rational generating functions (April 21)
Barvinok’s counting algorithm (April 28)
Introduction to parametric integer programming (May 5)
Exercises
Some of the exercises might look a little tough: we shall discuss them in the class. Generally, these exercises are intended to cover some extra topics, which are closely related to those from the lecture but have not been considered there.
February 26: Exercise sheet #1
March 5: Exercise sheet #2
March 12: Exercise sheet #3
March 19: Exercise sheet #4
March 26: Exercise sheet #5
April 1: Exercise sheet #6
April 8: Exercise sheet #7
April 21: Exercise sheet #8
April 28: Exercise sheet #9
May 6: Exercise sheet #10
May 13: Exercise sheet #11