CIMPA-UNESCO-PHILIPPINES 2009
ABSTRACTS OF LECTURES
Christine Bachoc, Bordeaux I, France
http://www.ufr-mi.u-bordeaux.fr/~bachoc/
Semidefinite programming, harmonic analysis and coding theory
We will try to present a general framework based on representation theory that obtains upper bounds for sphere packing problems from semidefinite programming. We will first review on the classical cases of two-point homogeneous spaces dealt with Delsarte linear programming method, with emphasis on the connections with the orthogonal polynomials in one variable. We shall recall the most beautiful cases were some explicit polynomials give exact bounds and proofs of optimality and uniqueness of some codes.
Then we will show how to extend this method to more general spaces, introducing semidefinite programming bounds and orthogonal polynomials with several variables. We will review many cases, where this method allows either to strengthen the Delsarte method, or to treat spaces that could not be dealt with before.
Eiichi Bannai, Kyushu University, Japan
http://hyoka.ofc.kyushu-u.ac.jp/search/details/K000379/english.html
Review of spherical designs
Spherical designs are an analytic generalization of combinatorial designs. They bear connections to numerical integration, euclidean lattices, and modular forms. The course will survey both construction and bounds on the size.
Henry Cohn, Microsoft Research, USA
http://research.microsoft.com/~cohn/
Distribution of points on spheres
One natural generalization of sphere packing is the energy mimimization problem: given some potential function depending on the pairwise distances between points, how should the points be arranged so as to minimize the total energy? This problem arises naturally in geometry, information theory and physics. Abhinav Kumar and I have introduced the idea of a universally optimal configuration (for example, all inverse power laws). This gives a natural notion of the best way to distribute points on a surface such as a sphere or in space. The first class studies universal optimality theoretically, the second analyzes a surprising example in detail, and the third collects numerical evidence from massive computer searches and examines many interesting point configurations.
William Martin, Worcester Polytechnic Institute, USA
Terwilliger algebras in coding theory
In the seventies Philippe Delsarte in a seminal work developed a method initially aimed at bounding codes over finite fields, that yields upper bounds for the cardinality of codes with given minimal distance as a solution of a linear program. This method, also called the Delsarte method, or polynomial methods, was developed in the framework of Association Schemes, which is the most general framework dealing with finite metric spaces and was also lined to Lovasz theta number by A. Schrijver. This method also obtains bounds in more general situations, such as lower bounds for the size of combinatorial designs.
Frank Vallentin, CWI, Amsterdam, the Netherlands
http://homepages.cwi.nl/~vallenti/
Applications of semidefinite programming
Semidefinite programming can be applied to a variety of problems in geometric and algebraic combinatorics. We will present three examples in detail: constructing sphere coverings, finding upper bounds for packing problems, and computing low distortion embeddings of finite metric spaces.
The sphere covering problem is a classical problem in the geometry of numbers. Roughly speaking, it is concerned with minimizing the number of unit spheres which are need to cover arbitrary large but finite regions of n-dimensional Euclidean space. If one restricts the problem to the case when the centers of the spheres form a periodic point set one can solve the problem computationally using a mixture of polyhedral combinatorics and semidefinite programming.
One can formulate many problems in combinatorial optimization and geometry as a packing problem in an underlying metric space. Examples include the kissing number problem of the stability number of a graph. We will explain a generic method based on semidefinite programming and harmonic analysis to find upper bounds for packing in compact metric spaces.
The theory of low distortion embeddings of finite metric spaces has found many applications in theoretical computer science in the last years. Especially embeddings of finite graphs where the metric is given by the shortest path have been used to design approximation algorithms. The determination of an embedding with lowest distortion can be done by semidefinite programming. If the graph has structure, for instance symmetry or high girth, one can apply techniques from algebraic combinatorics and orthogonal polynomials to prove some analytic properties of the optimal embedding.