When and where

When: November 10, 2006. 11:00-17:00.
Where: Gorlaeus Laboratorium, Universiteit Leiden, Einsteinweg 55. (English version)
11:00 - 12:00: zaal 3, Gorlaeus
13:30 - 17:00: zaal 1, Gorlaeus

11:00-12:00	Hendrik W. Lenstra (Universiteit Leiden)   A new type of lattices. Abstract. The lecture will start by recalling how one can use a lattice basis reduction algorithm for solving systems of linear equations over the ring of integers. An analysis of this application suggests that one can more appropriately handle it by means of a new notion of lattice, for which the length function takes values in an ordered vector space of dimension greater than one. The full theory of these generalized lattices, as well as the corresponding basis reduction algorithms, remain to be developed. No previous knowledge of lattices is necessary for following the lecture.
12:00-13:30	Lunch
13:30-14:30	Phong Nguyen (École Normale Supérieure)   Hermite's constant and lattice reduction algorithms. Abstract. Lattice reduction is a computationally hard problem of interest to both public-key cryptography and public-key cryptanalysis. Despite its importance, extremely few algorithms are known. In this talk, we will survey all lattice reduction algorithms known, and we will try to speculate on future developments. In doing so, we will emphasize a connection between those algorithms and the historical mathematical problem of bounding Hermite's constant.
14:45-15:45	Friedrich Eisenbrand (Universität Paderborn)   Integer programming: Results in fixed dimension Abstract. In this lecture we will survey results on integer programming in fixed dimension which are obtained by using lattices and lattice basis reduction techniques. After we review the basic principles which lead to polynomial algorithms for integer programming, we also survey structural results concerning the integer hull and outline recent algorithms which show that integer programming in fixed dimension with a fixed number of constraints can be solved with a linear number of arithmetic operations.
16:00-17:00	Karen Aardal (Centrum voor Wiskunde en Informatica and TU Eindhoven)   Lattices and integer programming formulations. Abstract. We consider the problem of determining whether the system of equations Ax = d has an integer solution x satisfying 0 <= x <= u. We reformulate the problem using a reduced basis for a certain lattice. We then take a closer look at the special case where the matrix A has one row. We observe that a certain input structure makes the original formulation computationally hard even in low dimension. The reduced basis used in the reformulation detects this structure, and enables us to search for a feasible solution effectively. We explain this theoretically, both for the reformulation as well as for the original formulation.
17:00	Reception

• NWO - Nederlandse Organisatie voor Wetenschappelijk Onderzoek
• The DIAMANT home page
• Intercity Number Theory Seminars

Participation is for free, and there is no registration.

All further questions to: Karen Aardal or Hendrik W. Lenstra