Monday, October 5, 2015 - 19:00
1 hour (actually 50 minutes)
President's Suites C&D (Bill Moore Student Success Center First Level)
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.