Average-case optimization: search vs. decision

Abstract: For many optimization problems, we lack time-efficient algorithms; in many cases this is true even for "average-case" inputs from simple data models. To what extent can tools for complexity theory be adapted to this average-case setting? In this talk, I will focus on a very basic tool from complexity: replacing a search/optimization problem with a yes/no decision problem. This approach has been successful via the study of "planted" average-case inputs; however it fails to address many problems of interest. In this talk I will describe some of these optimization problems, explain the current state-of-the art approach along with some shortcomings, and suggest an alternative approach with (perhaps unfortunate) ties to Ramsey theory.

Tselil Schramm - Bio

Tselil Schramm is an assistant professor of Statistics at Stanford University. Before joining Stanford, she received her PhD from U.C. Berkeley and was also a postdoc at Harvard and MIT. She is broadly interested in the theory of algorithms, optimization, and computational complexity, especially for problems arising in statistics. Her work aims to develop algorithmic tools for high-dimensional estimation problems and to characterize and explain information-computation tradeoffs.