**Friday, 16:15 - 16:40 h, Room: H 2038**

**Dion Gijswijt**

Symmetric semidefinite programs based on tuples

**Abstract:**

The independence number in graphs can be bounded using semidefinite programming. Symmetries of the graph can be used to reduce the size of the SDP. A dramatic example of this occurs in coding theory, where the LovĂˇsz theta number for exponentially large graphs reduces to a polynomial sized LP (Delsarte bound) by virtue of the large symmetry group of the Hamming space.

Here we discuss stronger bounds, related to the Lasserre hierarchy, that involve tuples of vertices of the graph. We show efficient methods to apply symmetry reduction in this case. An explicit result (joint work with A. Schrijver and H. Mittelmann) gives improved bounds on binary codes using four-tuples, and shows that the quadruply shortened Golay code is optimal.

Talk 3 of the invited session Fri.3.H 2038

**"Algebraic symmetry in semidefinite programming"** [...]

Cluster 4

**"Conic programming"** [...]