# Pareto Optimal Solutions for Smooth Analysts

 COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I Topic: Pareto Optimal Solutions for Smooth Analysts Speaker: Ryan O'Donnell Affiliation: Carnegie Mellon University; Member, School of Mathematics Date: Monday, March 21 Time/Room: 11:15am - 12:15pm/West Bldg. Lecture Hall

Consider an optimization problem with n binary variables and d+1 linear objective functions. Each valid solution x in {0,1}^n gives rise to an objective vector in R^{d+1}, and one often wants to enumerate the Pareto optima among these. In the worst case there may be exponentially many Pareto optima; however, it was recently shown that in (a generalization of) the smoothed analysis framework, the expected number is polynomial in n. Unfortunately, the bound obtained had a rather bad dependence on d; roughly n^{d^d}. In this paper we show a significantly improved bound of n^{2d}. Our proof involves a novel use of the union bound. This is joint work with Ankur Moitra of MIT.