"Towards Theoretical models of natural inputs: aiming to bridge the Theory/AI divide"
Avrim Blum, Professor of Computer Science, Carnegie Mellon University
Thursday, May 1, 2014 at 4:00 P.M.
Room 368 (CIT 3rd Floor)
Theoretical Computer Science has become particularly adept at proving problems hard to solve or even to approximate well in the worst case; yet this does not make those problems disappear, and in many domains heuristic methods have been developed that work quite well in practice. This brings up the question of how theory can best contribute to our understanding of algorithms for such problems when worst-case analysis is too pessimistic and simple probabilistic models are on the other hand too optimistic or just inappropriate. In this talk I will discuss a few vignettes, centered around problems of clustering, finding equilibria, and privacy-preserving data analysis. One theme in part of this work is that often when AI problems such as clustering are formulated as optimization tasks, the objective being optimized is really a proxy for some other underlying goal. In such cases, implicitly-assumed connections between the proxy and underlying goal (which one would want to hold for the formulation to be reasonable) will sometimes imply additional structure that algorithms can use to bypass worst-case approximation barriers.
Host: Philip Klein
The talk can be viewed live here