Learning, Algorithm Design and Beyond Worst-Case Analysis

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

In computational complexity theory, the performance of an algorithm is traditionally defined by its worst-case resource usage as the size of the input tends to infinity. In practice, this asymptotic worst-case measure may be inappropriate for several reasons: the worst-case performance may occur only for contrived instances that never occur in practice; the instances occurring in practice may have special structural features; the average-case performance of the algorithm may be much better than its worst case; or heuristic algorithms may empirically be observed to perform well. The workshop will focus on these non-worst-case phenomena. It will explore probabilistic models of the input distribution, structured classes of inputs such as planted models, and empirical measurement of performance. The goal will be to provide tools best suited for the practical evaluation of algorithms. The workshop will enhance communication among the mathematics, computer science, statistics and operations research communities. It will be open to all potential participants, and the workshop findings (including video recordings of presentations) will be distributed to the public for comment and engagement. The organizers will encourage students to attend the workshop, and will actively recruit scientists from a diversity of backgrounds to contribute to a wide range of applications.