HUJI The Hebrew University of Jerusalem

Welcome to the Einstein Institute of Mathematics

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

Center for Theoretical Computer Science and Discrete Mathematics
Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

The Hebrew University Center for Theoretical Computer Science and Discrete Mathematics invites you to this year's Erdős Lecture in Discrete Mathematics and Theoretical Computer Science

Prof. Henry Cohn (Microsoft Research)


Location: Einstein Institute of Mathematics
Lectures:
  1. Fast Matrix Multiplication Using Representation Theory
    Monday, March 31st, 11:00,   Math 110
  2. Mysteries of Euclidean Sphere Packing Bounds
    Wednesday, April 2nd, 10:30,   Math 110
  3. Universally 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 Strassen showed 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 by Coppersmith and Winograd in 1986) reaches exponent 2.376. Chris Umans and I proposed using the representation theory of finite groups to develop fast algorithms. Together with Bobby Kleinberg and Balazs 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
| Israel Journal of Mathematics | Journal d'Analyse Mathematique |
Mathematics and Computer Science Library | Faculty of Science | The Hebrew University of Jerusalem |

Comments to: Naavah Levin, email: naavah at math.huji.ac.il
Design, construction & editing: Naavah Levin
Background image © copyright 1997 by Xah Lee, used with permission.
URL: http://www.ma.huji.ac.il/
Last updated: March 23rd, 2008