Frontiers in Science lecture - Physics, Information and Computation

Series
Other Talks
Time
Monday, October 5, 2015 - 7:00pm for 1 hour (actually 50 minutes)
Location
President's Suites C&D (Bill Moore Student Success Center First Level)
Speaker
Amir Dembo – Stanford University
Organizer
Prasad Tetali

Please Note: Light refreshments at 6:30pm

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.