UVictoria Probability and Dynamics Seminar: Souvik Ray

In this talk, we consider a notion of stability for solutions of random optimization problems based on small perturbations of the input data and inspired by the technique for proving CLT using Stein's method as illustrated with examples by Chatterjee (2008). This notion of stability is closely related with the size of near-optimal solution sets for those optimization problems. We establish this notion of stability for a number of settings, such as branching random walk, the Sherrington--Kirkpatrick model of mean-field spin glasses, the Edwards--Anderson model of short-range spin glasses, the Wigner and Wishart ensemble of random matrices and combinatorial optimization problems like TSP / MST / MMP on weighted complete graphs and Euclidean spaces.