As the main technical part of this talk, I will discuss one of our recent work on the smoothed analysis of multi-objective optimization. In particular, I will show that the number of Pareto optima in a binary optimization problem with a constant number of linear objective functions is polynomial in the smoothed model. I will also take this opportunity to highlight another recent result on the smoothed analysis of P.A.C. learning. I will then conclude the talk by drawing the contrast between these optimization problems and equilibrium computation in game theory and mathematical economics from the lens of smoothed analysis.
Joint work with Adam Kalai (Microsoft New England Lab), Heiko Roglin (Maastricht University), Alex Samorodnitsky (Hebrew U. ) as well as Daniel Spielman(Yale), Xi Chen (USC), and Xiaotie Deng (City University of Hong Kong).