Physics, information, and Computation

Physics, information, and Computation

Dembo_8x11A talk by Professor Amir Dembo of Stanford University.

Theoretical models of disordered materials yield precise predictions about the efficiency of communication codes and the typical complexity of certain combinatorial optimization problems. The underlying common structure is that of many discrete variables, whose interaction is represented by a random ‘tree like’ sparse graph.
We review recent progress in proving such predictions and the related algorithmic insights gained from it.

This talk is based on joint works with Andrea Montanari, Allan Sly and Nike Sun.

Amir Dembo is the Marjorie Mhoon Fair Professor of Quantitative Science (in Mathematics and Statistics) at Stanford University. He received the B.Sc and D.Sc. degrees in electrical engineering from the Technion-Israel Institute of Technology, Haifa in 1980, 1986 respectively. Dr. Dembo held visiting positions at U. Paris 7, U. Paris 6, Technion, Courant Institute, MSRI, Weizmann Institute and most recently at U. Paris 9. Dr. Dembo advised 15 Ph.D. students and co-authored more than 100 technical publications, including the book, “Large Deviations Techniques and Applications”, (Second Edition, Springer-Verlag, 1998, with O. Zeitouni). He is a fellow of the IMS, was a special invited IMS medallion lecturer (2005), an invited speaker at the International Congress of Mathematicians (2006) and the invited Levy lecturer of the Bernouli society(2009). Dr. Dembo worked in a number of areas including information theory, signal processing and bio-molecular sequence analysis. His current research interests are in probability theory and its relations with statistical physics.