Thursday,
October 7, 4:15 p.m. PSA 118
Frank Vallentin
Institute of Applied Mathematics, Technical University Delft
Convex Optimization, Harmonic Analysis and Discrete Geometry
(this talk is also a colloquium)
Abstract
Starting point of my talk are approximation algorithms for NP-hard problems
in combinatorial optimization which are based on semidefinite programming
(SDP), a recent and powerful method in convex optimization. One example is
the theta number of Lovasz which provides an upper bound for the largest
size of an independent set of finite graphs based on a solution of a
semidefinite program. Many problems in extremal discrete geometry can be
formulated in this way but for infinite geometric graphs. A famous example is
the kissing number problem which goes back to a discussion of Newton and
Gregory in 1692: What is the maximum number of non-overlapping unit balls
that can simultaneously touch a central unit ball? To tackle this problem we
generalize the theta number (and strengthenings based on SDP hierarchies) to
infinite graphs which yields an infinite-dimensional semidefinite program.
By using symmetries and tools from harmonic analysis it turns out that one
can solve these semidefinite programs by computer giving the best known
upper bounds in dimensions up to 24.
