Graph expansion and communication complexity of algorithms

Ran Raz
Weizmann Institute of Science; Member, Institute for Advanced Study Location
March 11, 2014
The Martians built an amazingly fast computer and they run it to answer the great question of life, the universe and everything. They claim that the answer is 42. Will they be able to convince us that this is the right answer, assuming that we do not have sufficient computational power to run the computation ourselves, and that we do not trust Martians? The problem of verifiable computation delegation is a central problem in cryptography.

The Sherrington-Kirkpatrick model and its diluted version I

Dmitry Panchenko
Texas A&M University
March 11, 2014
I will talk about two types of random processes -- the classical Sherrington-Kirkpatrick (SK) model of spin glasses and its diluted version. One of the main goals in these models is to find a formula for the maximum of the process, or the free energy, in the limit when the size of the system is getting large. The answer depends on understanding the structure of the Gibbs measure in a certain sense, and this structure is expected to be described by the so called Parisi solution in the SK model and Mézard-Parisi solution in the diluted SK model.

The Sherrington-Kirkpatrick model and its diluted version II

Dmitry Panchenko
Texas A&M University
March 12, 2014
I will talk about two types of random processes -- the classical Sherrington-Kirkpatrick (SK) model of spin glasses and its diluted version. One of the main goals in these models is to find a formula for the maximum of the process, or the free energy, in the limit when the size of the system is getting large. The answer depends on understanding the structure of the Gibbs measure in a certain sense, and this structure is expected to be described by the so called Parisi solution in the SK model and Mézard-Parisi solution in the diluted SK model.

The Brownian motion as the limit of a deterministic system of hard-spheres

Thierry Bodineau
École Polytechnique
March 12, 2014
We provide a derivation of the brownian motion as the hydrodynamic limit of a diluted deterministic system of hard-spheres (in the Boltzmann-Grad limit). We use the linear Boltzmann equation as an intermediate level of description for one tagged particle in a gas close to global equilibrium.

S.T. Lee Lecture: After Syria: The Future of the Responsibility to Protect

Gareth Evans
Chancellor of the Australian National University and former Foreign Minister of Australia
March 12, 2014
In this lecture, Gareth Evans, Chancellor of the Australian National University and former Foreign Minister of Australia, posits whether it is possible to end, once and for all, genocide and other major crimes against humanity occurring behind sovereign state walls to ensure that there will never again be another Cambodia, Rwanda, Srebrenica, or Darfur. Evans also questions if the new principle of "the responsibility to protect" (R2P), which was unanimously embraced by the U.N.

The matching polytope has exponential extension complexity

Thomas Rothvoss
University of Washington, Seattle
March 17, 2014
A popular method in combinatorial optimization is to express polytopes \(P\), which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so called extension complexity. However, the central question in this field remained wide open: can the perfect matching polytope be written as an LP with polynomially many constraints?

Graph expansion and communication complexity of algorithms

Olga Holtz
University of California, Berkeley; Member, School of Mathematics
March 18, 2014
In joint work with Ballard, Demmel, and Schwartz, we showed the communication cost of algorithms (also known as I/O-complexity) to be closely related to the small-set expansion properties of the corresponding computation graphs. This graph expansion approach produces first lower bounds on the communication costs of Strassen's and other fast matrix multiplication algorithms. I will discuss both the general method and its concrete implementations.