Session: Any-dimensional symmetric optimization
Chair: Eitan Levin
Cluster: Conic and Semidefinite Optimization
Talk 1: Any-dimensional polynomial optimization
Speaker: Eitan Levin
Abstract: Optimization problems in many applications arise as sequences indexed by dimension. Relaxations producing bounds for such problems should then similarly be defined for all relevant dimensions, and bounds should be produced on their limiting optimal values. For example, in combinatorics convex relaxations for graph parameters need to be defined for graphs of all sizes, and inequalities between graph densities need to be certified for graphs of increasing size. In (quantum) information theory, relaxations should be defined for distributions on any number of (qu)bits. And in signal processing, regularizers should be defined for signals of any length. We present a framework to systematically study optimization problems which are defined for any dimension, fit tractable relaxations for them from data which are defined for all problem sizes, and derive lower bounds on their asymptotic values. We do so by observing that these problems are described in a “free” way which makes it obvious how to instantiate them in any dimension. We explain how such free descriptions arise from the phenomenon of representation stability, and study their properties by considering the relations between problems across dimensions and their symmetries. We present two consequences of our framework. First, we show that sequences of semidefinite relaxations of many polynomial problems stabilize in size, allowing us to derive bounds on their asymptotic optimal values. Second, we derive families of functions defined for all dimensions described by finitely-many parameters, allowing us to fit such functions to data in a few small dimensions and instantiate the fitted function in any other dimension.
Talk 2: Optimality Conditions for Extremal Combinatorics
Speaker: Daniel Brosch
Abstract: Given a sequence of graphs of increasing size $\mathcal{G} = (G_1,G_2,G_3,\ldots)$, we define the density of a finite graph $H$ in $\mathcal{G}$ as the limit of the subgraph densities of $H$ in the finite graphs $G_i$. By considering functions which assign $\mathcal{G}$ a real linear combination of subgraph densities, we can formulate a wide variety of problems of (asymptotic) extremal graph theory in the form $\min_{\mathcal{G}} \{f(\mathcal{G})\mid g(\mathcal{G})\geq 0, h(\mathcal{G})= 0\}$. We define derivations of graph density functions, study the tangent cone of such problems, and prove optimality conditions for the constrained and unconstrained case. Finally, we consider the consequences for the geometry of the space of graph limits, as well as open conjectures such as Sidorenko's conjecture and the Caccetta-Häggkvist conjecture.
Talk 3: Semidefinite bounds for covering codes
Speaker: Sven Polak
Abstract: Let $K_q(n,r)$ denote the minimum size of a $q$-ary \emph{covering code} of word length $n$ and covering radius $r$. In other words, $K_q(n,r)$ is the minimum size of a set of $q$-ary codewords of length $n$ such that the Hamming balls of radius $r$ around the codewords cover the Hamming space $\{0,\ldots,q-1\}^n$. The special case $K_3(n,1)$ is often referred to as the \emph{football pool problem}, as it is equivalent to finding a set of forecasts on $n$ football matches that is guaranteed to contain a forecast with at most one wrong outcome. In this work, we build and expand upon the work of Gijswijt (2005), who introduced a semidefinite programming lower bound on $K_q(n,r)$ via matrix cuts. We develop techniques that strengthen this bound, by introducing new semidefinite constraints inspired by Lasserre's hierarchy for 0-1 programs and symmetry reduction methods, and a more powerful objective function. The techniques lead to sharper lower bounds, setting new records across a broad range of values of $q$, $n$, and $r$. This talk is based on joint work with Dion Gijswijt.
