Conference Agenda

Symmetry arises quite naturally in many computational problems and from a computational perspective, it allows to reduce the complexity of problems. The mini-symposium aims to presents various instances of computational problems in real algebraic geometry, where symmetry playes an important role.

The completely positive matrices form a subcone of the cone of positive semidefinite matrices over which optimization is NP-hard, but which allows us to provide exact formulations for many combinatorial optimization problems: if, for instance, one replaces positive semidefinite matrices by completely positive matrices in the Lovász theta number, the resulting parameter is equal to the independence number instead of being just an upper bound for it.

The Lovász theta number can be extended to distance graphs on infinite spaces, like the unit distance graph of R^n, whose vertices are all points of R^n and in which two vertices are adjacent if they are at distance 1 from each other. In the case of the unit distance graph, the Lovász theta number provides an upper bound for the maximum density m_1(R^n) that a measurable subset of R^n not containing points at distance 1 can have. I will define the cone of completely positive operators on a Hilbert space and show how it can be used to give an exact formulation for parameters such as m_1(R^n), in analogy with the situation of finite graphs.

This exact formulation can then be used to compute better upper bounds and also to give alternative proofs of results such as the Turing computability of m_1(R^n).

(Joint work with Evan DeCorte and Frank Vallentin.)

The kissing number of spherical caps asks for the maximal number of pairwise non-overlapping unit spheres that can simultaneously touch a central spherical cap in n-dimensional Euclidean space. We consider especially the kissing number of the hemisphere in dimension 8. The kissing number of hemispheres provides less symmetries than the kissing number of unit spheres, which makes the problem more difficult.

The kissing number problem of spheres coincides with the problem of finding a maximal spherical code with minimal angular distance pi/3. The famous configuration of 240 points of unit spheres in dimension 8 given by the root lattice E8, which is an optimal spherical code of minimal angular distance pi/3, is unique up to isometry. From these 240 points we get a configuration on the hemisphere with 183 pairwise non-overlapping unit spheres. Bachoc and Vallentin determined an upper bound of 183.012 using semidefinite optimization, hence the kissing number of the hemisphere in dimension 8 is 183.

Using the semidefinite program of Bachoc and Vallentin we obtained a sharp numerical bound of 183. Based on this floating point solution and the configuration given by the E8 lattice we study uniqueness. This is a joint work with David de Laat and Philippe Moustrou.