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. I will survey some settings in which this approach has been successful via the study of "planted" average-case inputs. Then, I will describe some problems for which I do not know of a natural average-case decision problem, with (perhaps unfortunate) ties to Ramsey theory.
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.