The Morris Loeb Lecture in Physics: Marc Mézard

April 18, 2014


Ecole Normale Supérieure, Paris

Colloquium: "The spin glass cornucopia"

Monday, April 28 @ 4:15pm
Jefferson 250, 17 Oxford Street, Cambridge

For more than 30 years, the spin glass puzzle has stimulated a large activity in statistical physics, and led to several breakthroughs. While the puzzle of spin glass materials is still not fully solved, their theoretical analysis has created a very rich conceptual framework, as well as powerful techniques, to study emergent properties of strongly disordered and interacting systems. These have been successfully applied to a broad spectrum of other disciplines, from finance to computer science and information theory, where slow - glassy - dynamics and phase transitions play a key role. The talk will survey this spin glass saga, focusing on its developments outside of physics.

Lecture I: "Phase transitions in hard computer science problems"

Tuesday, April 29 @ 2:30pm
Jefferson 250, 17 Oxford Street, Cambridge

A new field of research is rapidly expanding at the crossroad between statistical physics, information theory and combinatorial optimization. It deals with problems which are very important in each of these fields, like spin glasses, error correction, or satisfiability. In recent years, it has been realized that physical phenomena, familiar from glass phenomenology, occur in large classes of algorithms that have been developed to study some of the hardest computer science problems. Realizing that extreme slowdown and glassy phase transitions occur in computer programs is interesting both theoretically, as it opens new perspectives to the study of algorithmic complexity, as well as practically : it allows to develop new kind of efficient algorithms, inspired from insights obtained through the "replica method" and the "cavity method". This talk will survey these recent developments, focusing on the conceptual leap induced by the use of spin glass theory in hard constraint satisfaction problems.

Lecture II: "Occam’s razor in massive data acquisition: a statistical physics approach"

Wednesday, April 30 @ 2:00pm
Science Center Hall A, One Oxford Street, Cambridge

Science is facing several challenges related to data explosion. How to acquire a large amount of information in short time? How to extract significant data? In recent years, studies in compressed sensing have triggered very interesting developments on these issues. Compressed sensing consists in sampling a sparse signal at low rate, and later using computational power for its exact reconstruction, so that only the necessary information is measured. Currently used reconstruction techniques are, however, limited to acquisition rates larger than the true density of the signal. We shall describe new procedures, based on a statistical physics analysis, which is able to reconstruct exactly the signal with a number of measurements that approaches the theoretical limit for large systems.