AF: Medium: Smoothed Analysis for Optimization and Games

Many algorithms and heuristics that work well in practice have poor performance under the worst-case analysis due to delicate pathological instances that one may never encounter, practically speaking, creating a huge theory-practice gap in the understanding of such algorithms. One of the best known such examples is the Simplex algorithm for Linear Programming, which is widely used in practice but has exponential running time in the worst case. To provide a more realistic explanation for its success, Spielman and Teng introduced the smoothed-analysis framework, which can be viewed as a hybrid of the classical worst-case and average-case analysis. The smoothed-analysis framework has since been applied to a range of problems in areas such as mathematical programming, machine learning, numerical analysis, etc. Among them, the smoothed analysis of algorithms and problems that arise from combinatorial optimization and algorithmic game theory has been studied intensively during the past decade. However, despite much progress, some of the most fundamental problems remain wide open, and tools currently available for performing smoothed analysis remain limited. This project plans to explore some of the new directions and challenging problems that have emerged in the smoothed analysis of algorithms for optimization and game-theoretic problems. The goal of the project is to develop new techniques that will enable better understanding of a broad range of algorithms and problems through the lens of smoothed analysis. The research team is broadly disseminating new results from the project by giving talks at interdisciplinary conferences, major universities and research labs, and by developing new advanced courses on smoothed analysis. The interdisciplinary nature of the project is likely to appeal to students with diverse backgrounds. In addition to advising and mentoring Ph.D. students, the research team is actively involving undergraduate students in accessible research projects. The research team is also participating in outreach activities that may help develop interest in Computer Science from a broader population.

For the smoothed analysis of combinatorial-optimization problems, the research team is focusing on the local-search paradigm. A core problem that the team plans to study is the smoothed complexity of the FLIP algorithm for Local Maximum Constraint Satisfaction problems, including examples such as MAX-CUT and MAX-3SAT. The team also plans to study the smoothed complexity of heuristics for the Traveling Salesman Problem (TSP), such as k-Opt. Improved understanding of k-Opt may shed new light on the smoothed analysis of Lin-Kernighan, one of the most widely used heuristics for TSP in practice. For the smoothed analysis of algorithms and problems from game theory and economics, the team is working to investigate the smoothed complexity of Policy and Value Iteration for solving Markov decision processes and more generally, stochastic games. The team is also working to establish unconditional lower bounds for the smoothed complexity of the Lemke-Howson algorithm for bimatrix games and the global Newton method of Smale for market equilibria.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.