February 25 - 29, 2008
Organizers: Henry Cohn, Mathieu Dutour Sikiric, Achill Schürmann, Frank Vallentin
Description: The linear programming bounds (LP bounds), established by Delsarte in 1973, and their recent extension, the semidefinite programming bounds (SDP bounds), give the strongest known upper bounds for packing problems in metric spaces.
Topics and Goal:
The LP and SDP bound technique amounts to proving an upper bound for a packing problem by finding an optimal solution of a specific LP or SDP problem. It turned out that although the LP and the SDP bounds are obtained from convex optimization problems they are usually very difficult to solve numerically. Where does this numerical instability come from and how can one deal with it? Under which conditions do LP/SDP bounds give sharp results? One very specific case is the kissing number in dimension 4. In 2003 Musin used the LP bound together with some geometric insight to show that the kissing number in dimension 4 equals 24. Bachoc and Vallentin showed that one can get a simpler proof of this fact by using the SDP bound. It is widely believed that the kissing configuration in dimension 4 is unique. Is it possible to use the SDP bound to show that the vertices of the 24-cell give the unique optimal kissing configuration in dimension 4? Cohn and Elkies showed in 2003 that the LP bound also applies to the non-compact Euclidean space Rn. They found new best-known upper bounds for the sphere packing density in dimension 4, ..., 36. Is it possible that the LP bound of Cohn and Elkies can be used to give asymptotic results? Can one use SDP bounds to give asymptotic results?
Person |
Affiliation |
Period of stay |
Christine Bachoc | Université Bordeaux 1 | |
Robert Baier | Universität Bayreuth | |
Eiichi Bannai | ||
Carsten Carstensen | ||
Jean Creignou | Université de Bordeaux 1 | |
Hervé Diet | Université de Bordeaux 1 | |
Tzanko Donchev | ||
Fernando Mario de Oliveira Filho | CWI | |
Armin Fügenschuh | TU Darmstadt | |
Dion Gijswijt | Leiden University | |
Gregory Kabatiansky | ||
Omar Lakkis | University of Sussex | |
Thomas Lorenz | Universität Heidelberg | |
Oleg Musin | University of Texas | |
Christoph Ortner | Computing Laboratory | |
Pablo Parrilo | Massachusetts Institute of Technology | |
Florian Pfender | Universität Rostock | |
Dirk Praetorius | Vienna University of Technology | |
Janosch Rieger | Universität Bielefeld | |
Marco Romito | Università di Firenze | |
Alex Samorodnitsky | The Hebrew University of Jerusalem | |
Lars Schewe | TU Darmstadt | |
Achill Schürmann | Universität Magdeburg | |
Mathieu Dutour Sikiric | ||
Makoto Tagami | Universität Magdeburg | |
Frank Vallentin |