BMS Summer School: Packings, Coverings, and Embeddings

Lecturer
Prof. Dr. Frank Vallentin

Teaching assistants
M.Sc. Maria Dostert, M.Sc. Jan Rolfes

Summary
It will be shown how to use semidefinite optimization in discrete geometry. Covered topics will include: Finding upper bounds for geometric packing problems, constructing optimal lattice sphere coverings, and computing low-distortion embeddings of finite metric spaces into Euclidean spaces.

Problem Sheets
Sheet 1: Conic optimization
Sheet 2: Embeddings
Sheet 3: Coverings
Sheet 4: Packings

Software
B. Borchers – CSDP Solver
A. Garber, A. Schürmann, F. Vallentin – scc (secondary cone cruiser)

Literature
General:
M. Laurent, F. Vallentin – Semidefinite Optimization, 2012
Conic optimization:
A. Nemirovski – Advances in convex optimization: conic programming, 2007
D. de Laat – A ten page introduction to conic optimization, 2015
Embeddings:
S. Hoory, N. Linial, A. Wigderson – Expander graphs and their applications, 2006
J. Matousek – Lectures on Discrete Geometry (Chapter 15), 2005
F. Vallentin – Optimal Embeddings of Distance Regular Graphs into Euclidean Spaces, 2008
Coverings:
A. Schürmann, F. Vallentin – Computational Approaches to Lattice Packing and Covering Problems, 2006
M. Dutour-Sikiric, A. Schürmann, F. Vallentin – A generalization of Voronoi’s reduction theory and its application, 2008
M. Dutour-Sikiric, A. Schürmann, F. Vallentin – Inhomogeneous extreme forms, 2012
Packings:
P.E.B. DeCorte, D. de Laat, F. Vallentin – Fourier analysis on finite groups and the Lovász theta-number of Cayley graphs, 2014
F.M. de Oliveira Filho, F. Vallentin – Mathematical optimization for packing problems, 2014