## 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
*