Mark Sellke (Harvard University)
Title: Algorithmic Spin Glass Theory.
Abstract: Mean field spin glasses are a family of random functions in high dimension. Originally developed to explore properties of disordered magnets, these models have found applications to a broad range of problems in computer science and statistics. Parisi’s theory of replica symmetry breaking predicts the global maximum value of these functions. In many setting, this has been rigorously confirmed by Talagrand and others. What about efficient algorithms? Namely, given a random high-dimensional optimization problem, can one efficiently compute an approximately optimal solution? What about sampling a uniformly random solution? I will review recent progress on this class of problems.
In Person
Location: Burnside Hall, Room 719A, 805 Rue Sherbrooke O, Montréal, QC H3A 2K6
Zoom Link: