Speakers

Christine Bachoc (University of Bordeaux)

Jop Briët (CWI Amsterdam)

Dion Gijswijt (CWI Amsterdam, Leiden University)

Achill Schürmann (TU Delft)

Renata Sotirov (Tilburg University)

Program

10h00-10h30 Welcome and coffee

10h30-11h15 Achill Schürmann

11h30-12h15 Jop Briët

12h30-14h00 lunch break

14h00-14h45 Dion Gijswijt

15h00-15h45 Renata Sotirov

16h00-16h45 Christine Bachoc

When and where?

Thursday, December 3, 2009

CWI Amsterdam,

Eulerzaal

Where is it?

Organizers

Dion Gijswijt (CWI Amsterdam, Leiden University) Monique Laurent (CWI Amsterdam, Tilburg University), Frank Vallentin (TU Delft, CWI Amsterdam)

Participants

Krzysztof Apt (CWI), Ali Asadi (TU Delft), Christine Bachoc (U Bordeaux), Alp Bassa (CWI), Mathieu Bogaerts (U Bruxelles), Niek Bouman (CWI), Jop Briet (CWI), Harry Buhrman (CWI), Edwin van Dam (U Tilburg), Cristian Dobre (U Tilburg), Jan Draisma (TU Eindhoven, CWI), Dion Gijswijt (CWI, U Leiden), Carlos Gonzalez, Etienne de Klerk (U Tilburg), Monique Laurent (CWI, U Tilburg), Arie Matsliah, Tobias Mueller (CWI), Marianna Nagy (U Tilburg), Fernando de Oliveira Filho (CWI), Guus Regts (CWI), Cordian Riener (U Frankfurt), Kees Roos (TU Delft), Giannicola Scarpa (CWI), Lex Schrijver (CWI, UvA), Achill Schuermann (TU Delft), Bib Silahali (TU Delft), Renata Sotirov (U Tilburg), Frank Vallentin (TU Delft, CWI), Antonios Varvitsiotis (CWI), Ronald de Wolf (CWI)

Titles and abstracts

Semidefinite constraints on k elements, binary codes and hypergraphs

Christine Bachoc

joint work with Gilles Zemor, Cordian Riener

Motivated by applications in coding theory where several pseudo-distances on k words are of interest, in particular in relation with the notion of list decoding, we shall discuss a generalization of Lovasz theta number to hypergraphs. In view of applications to the Hamming space, the symmetrization of the associated semidefinite program is essential and involves to understand the action of the stabilizer of several points in its automorphism group.

The positive semidefinite Grothendieck problem with rank constraint

Jop Briët

joint work with Fernando Mario de Oliveira Filho and Frank Vallentin

The positive semidefinite Grothendieck problem with rank-n-constraint is a problem that arose recently in the context of quantum non-local games. The case without rank constraint can be solved in polynomial time using semidefinite programming. In contrast, the case n=1 is NP-hard, as finding the maximum cut of a graph, one of Karp's 21 NP-complete problems, is a specific instance it. For this case Nesterov gave a polynomial-time approximation algorithm which is optimal under the assumption of the unique games conjecture. In this talk, we give a polynomial-time approximation algorithm for the full problem, where we allow n to be arbitrary. In addition, by using an improved analysis of Nesterov's algorithm we show that our algorithm is optimal under the assumption of the unique games conjecture.

SDP's for block codes: how to bring your algebra into block diagonal form

Dion Gijswijt

Let q be a fixed positive integer. Consider the set of matrices with rows and columns indexed by all q-ary words of length n, that are invariant under permuting the n positions in the words. We will give a formula for the block diagonalisation of this matrix *-algebra.This can be applied to semidefinite programming bounds for codes. In recent years, SDP has been succesfully applied to coding theory, resulting in improved bounds for specific instances and in hierarchies of increasingly tight bounds. There typically, the matrix variable of the SDP has exponential size, but runs over a highly symmetric matrix algebra. Given an explicit block diagonalisation of the algebra, the size of the matrices can then be reduced to make the SDP computationally tractable. Such a block diagonalisation is known in some cases, most notably for the Terwilliger algebra of the binary Hamming cube. We give a general method for finding a block diagonalisation for a class of algebras arising in coding theory. This includes the Terwilliger algebra of the (non)binary Hamming cube, algebras for Lee-distance codes and algebras from hierarchies of SDP bounds for binary codes.  

Energy minimizing point configurations

Achill Schürmann

Point configurations that minimize energy given by some pair potential function are a quite general mathematical model that occurs in diverse contexts, such as crystallography, electrostatics or computer graphics. In this talk we report on recent results for two of the most interesting cases: point sets in Euclidean spaces and on spheres. On the one hand we show how conjectural optimal configurations can be found using computer experiments, and how symmetries of some exceptional structures can be used to prove at least their local optimality. On the other hand we explain how linear and semidefinite programming bounds can (or could potentially) be used to estimate the minimum possible energy, and even certify global optimality in some exceptional cases.

Improved Semidefinite Programming Bounds for the Quadratic Assignment Problem

Renata Sotirov

joint work with Etienne de Klerk

The Quadratic Assignment Problem (QAP) is a well-known NP-hard problem, and even small instances are notoriously difficult to solve in practice. Semidefinite programming (SDP) bounds for the QAP were introduced in 1998. These bounds are quite strong, but computationally demandng. For QAP instances where the data matrices have large automorphism groups, the SDP bounds can be computed more efficiently, as was shown in: [E. de Klerk and R. Sotirov. Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Mathematical Programming A, (to appear)]. In this talk we show how one may obtain even stronger SDP bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.