Convex Optimization, Harmonic Analysis & Discrete Geometry
Listen now
Description
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.
More Episodes
Algebraic statistics advocates polynomial algebra as a tool for addressing problems in statistics and its applications. This connection is based on the fact that most statistical models are defined either parametrically or implicitly via polynomial equations. The idea is summarized by the phrase...
Published 04/28/11
Mathematical concepts are often difficult for students to acquire. This difficulty is evidenced by failure of knowledge to transfer from the learning situation to a novel isomorphic situation. What choice of instantiation most effectively facilitates successful transfer? One possibility is that...
Published 04/27/11
This presentation does not require previous knowledge of C*-algebras, labeled graphs, or group actions. A labeled graph over an alphabet consists of a directed graph together with a labeling map . One can associate a C*-algebra to a labeled graph in such a way that if the labeling is...
Published 04/08/11