Tselil Schramm

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...