DIAMANT/Spinoza Intercity Seminar on
Algebra and Symmetries in Combinatorics and Optimization

Friday June 30, 2006
11:00 - 17:00

Organization

This day is organized by the research group PNA1: Algorithms, Combinatorics and Optimization.
For information you may contact Monique Laurent (monique at cwi.nl) or Lex Schrijver (lex at cwi.nl).

Date and Place

Friday June 30, 2006
The seminar day takes place at the University of Amsterdam.
Roetersstraat 15, Room A-306. The room is located in building A, number 7 on the map here .

Registration

Participation is free. But registration is required to join the (free) lunch.
To register please send an email to Susanne van Dam (Susanne.van.Dam at cwi.nl).

Programme

10:30 - 11:00: Welcome with coffee
11:00 - 11:50: Vangelis Markakis
11:55 - 12:45: Markus Schweighofer
12:45 - 14:00: Lunch
14:00 - 14:50: Balazs Szegedy
15:00 - 15:50: Gabriele Nebe
16:10 - 17:00: Frank Vallentin

Speakers

Vangelis Markakis, University of Toronto
Title: On the Fourier spectrum of symmetric boolean functions (with applications to learning symmetric juntas)
Abstract: We prove a structural result on the low order spectrum of symmetric functions. In particular, we show that every symmetric boolean function on k variables, other than the constant and the parity functions, has a nonzero Fourier coefficient of order at least 1 and at most 4k/logk. Our work is motivated by the problem of learning juntas in the PAC model. A k-junta is a function of n variables that depends only on an unknown set of k variables. Our result implies the first n^{o(k)} algorithm for learning symmetric k-juntas under the uniform distribution.
Joint work with Mihalis Kolountzakis, Richard Lipton, Aranyak Mehta and Nisheeth Vishnoi.

Gabriele Nebe, University of Aachen
Title: Lattices and spherical designs
Abstract: A t-design lattice is a lattice whose minimal vectors form a spherical t-design (as introduced by Goethals and Seidel in 1977). For t at least 4 these lattices are local maxima for the density function. In the talk I will report on the classification of t-design lattices, which is known for t at least 4 and n at most 12, and for t at least 6, n at most 24 distinct from 23. There are only four 11-design lattices of dimension at least 2 known: The Leech lattice in dimension 24 and the 3 known unimodular 48-dimensional lattices with minimum 6. The existence of t-design lattices for t at least 12 and n > 1 is still open.
Joint work with Boris B. Venkov.

Markus Schweighofer, University of Konstanz
Title: Test sets for positivity of symmetric forms and sums of powers of linear forms
Abstract: Vlad Timofte showed recently that a symmetric real polynomial f of degree 2k in n variables is positive on R^n if and only if it is so on the subset of points with at most max{k,2} different components. For each fixed degree 2k, this yields a polynomial time algorithm to decide whether a symmetric real polynomial of degree 2k in several variables is nonnegative on R^n. Timofte's proof uses the theory of ordinary differential equations. We interprete Timofte's result as an equality of two convex cones and show that the equality of the dual cones is a statement about sums of powers of linear forms which is related to Hilbert identities and quadrature rules. We hope that this viewpoint might lead to an algebraic or combinatorial proof of Timofte's result and invite the audience to look together with us for such a proof.
Joint work with David Grimm.

Balazs Szegedy, Institute for Advanced Study, Princeton (USA)
Title: Group theoretic algorithms for fast matrix multiplication
Abstract: In 1969 Strassen discovered the surprising fact that it is possible to multiply two 2x2 matrices by using 7 multiplications. This leads to an algorithm which multiplies two nxn matrices with n^(2.81+o(1)) field operations. Coppersmith and Winograd in 1990 improved the constant 2.81 to 2.376 but the best constant is still unknown. We present group theoretic algorithms for matrix multiplication and we discuss underlying combinatorial problems.
Joint work with H. Cohn, R. Kleinberg and C. Umans.

Frank Vallentin, CWI, Amsterdam
Title: Upper bounds for kissing numbers by semidefinite programming
Abstract: In 1973 P. Delsarte introduced the so-called linear programming bound in order to find upper bounds for codes over finite fields with prescribed minimum distance. It turned out that this method can be generalized to compact two-point homogeneous spaces. One striking application of this is finding upper bounds for the kissing number. The kissing number problem asks for the largest number of unit spheres which one can arrange around a central unit sphere so that they all touch the central sphere. In 1979 Odlyzko and Sloane and independently Levenshtein gave upper bounds for the kissing number in dimension {4,...,24}.
In 2005 A. Schrijver demonstrated how one can use semidefinite programming to find better bounds for codes over finite fields. In the talk I show how one can generalize Schrijver's method for codes in compact homogeneous spaces. Especially, I will consider the kissing number problem. There we have strong numerically evidence that our new bound improves the one of Odlyzko and Sloane in dimensions {4,...24} \ {8, 24}.
Joint work with Christine Bachoc.

How to get there

From train station Amsterdam Centraal: take sneltram 51 (direction Amstelveen), or metro 53 (direction Gaasperplas), or metro 54 (direction Gein), till stop Weesperplein
From train station Amsterdam Amstel: take sneltram 51, or metro 53 or 54 (direction Centraal Station) till stop Weesperplein
From train station Duivendrecht: take metro 53 or 54 (direction Centraal Station) till stop Weesperplein
From train station Amsterdam Muiderpoort: take tram 7 (direction Sloterpark) till stop Korte 's-Gravesandestraat
You can find a map of the location of the seminar day here.

Sponsors

This event is sponsered by DIAMANT and the NWO-Spinoza project.

CWI DISCLAIMER