**
Welcome to the Einstein Institute of Mathematics**

Home | About | Staff | Studies | Colloquia & Events | Research | Services & Resources | Sites |

Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

**
Prof. Henry Cohn (Microsoft Research)
**

Location: Einstein Institute of Mathematics

Lectures:

Fast Matrix Multiplication Using Representation Theory

Monday, March 31st, 11:00, Math 110Mysteries of Euclidean Sphere Packing Bounds

Wednesday, April 2nd, 10:30, Math 110Universally Optimal Distribution of Points on Spheres

Thursday, April 3rd, 16:00, Math 2

Light refreshments will be served before each of the talks

Abstracts:

Fast Matrix Multiplication Using Representation Theory- How quickly can one multiply two large matrices? Surprisingly, this natural question has never been completely answered. In 1969
Volker Strassenshowed how to multiply n-by-n matrices in roughly n^2.81 operations, which was an amazing improvement over the obvious n^3 algorithm; currently the best method known (discovered byCoppersmith and Winogradin 1986) reaches exponent 2.376.Chris Umansand I proposed using the representation theory of finite groups to develop fast algorithms. Together withBobby KleinbergandBalazs Szegedy, we made some progress in this direction, and we have formulated several conjectures that would achieve exponent 2.

This talk will describe the framework, discuss what we can prove, and explain what we wish we could prove.

Mysteries of Euclidean Sphere Packing Bounds- Above dimension 3, the best sphere packing bounds known are all proved using some form of linear programming bounds. However, these bounds behave quite mysteriously. They appear to be sharp in 8 and 24 dimensions, yet no proof is known, despite tantalizing numerical clues. The asymptotic behavior of the bounds as the dimension tends to infinity also remains unclear. Furthermore, numerical calculations show unexpected and puzzling behavior.

In this talk, we'll explore what we don't understand about sphere packing bounds.

Universally Optimal Distribution of Points on Spheres- How should one distribute a certain number of points over a sphere, so that they are well separated from each other? One natural method is energy minimization: put an electric charge on each point and let them repel each other. This problem arises naturally in physics, but it extends to far more general spaces and potential functions; it can be viewed as a broad generalization of packing problems. Some of the most remarkable exceptional structures in mathematics (such as the E_8 root system, the Leech lattice minimal vectors, the Schlaefli configuration of 27 points in R^6 related to the 27 lines on a cubic surface, the icosahedron, and the regular 600-cell) are solutions of energy minimization problems of this sort. These examples have a rare property called universal optimality: they simultaneously minimize a broad class of potential functions.

This talk will survey what's known and conjectured about universally optimal configurations.

Reference:

Strassen, Volker: Gaussian elimination is not optimal.Numer. Math.13 1969 354--356.

Robinson, Sara: Toward an Optimal Algorithm for Matrix Multiplication.SIAM News, Volume 38, Number 9, November 2005

Back to the Math home page

Mathematics and Computer Science Library | Faculty of Science | The Hebrew University of Jerusalem |

Background image © copyright 1997 by Xah Lee, used with permission.