Title: The Distribution of Values in Combinatorial Optimization Problems

We study the distribution of objective values in a combinatorial optimization problem defined on the symmetric group. Our approach is to use techniques from representation theory to generate statistics on the quantity and relative location of good values for two prominent optimization problems, namely the Quadratic Assignment Problem (QAP) and the Traveling Salesman Problem (TSP).
This analysis shows us some very general, yet non-trivial properties of the optimization function, allows us to get guarantees for simple polynomial and non-polynomial approximation algorithms, and helps us to understand why some hard problems are simpler than others.
This is joint work with Alexander Barvinok.