Back to the Future: Going Beyond Worst Case Analysis

Saturday, Oct. 17, 2015 11:00 am11:25 am

Add to Calendar


Soon after demonstrating the ubiquity of NP-completeness in optimization, Dick Karp did pioneering work on average-case analysis of NP-hard problems as a way to explain the real-life performance of heuristics.  Though this line of work was substantially developed and extended in subsequent decades, the dominant paradigm in algorithm design remained worst-case analysis.  In recent years there is increasing recognition that in many exciting settings in algorithms design---especially related to machine learning and "big data"---the natural problems are intractable, and are often solved (successfully) at very large scales in practice by heuristics. The talk will survey problems in a host of application domains, and argue that new modes of analysis ---going beyond the worst-case---hold the key to further progress.