Universität Bonn

Workshop: "Linear and semidefinite programming bounds"


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?


Participants

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  
Wird geladen