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