"Worst-Case Running Times for Average-Case Algorithms."

Luis Filipe Coelho Antunes, Lance Fortnow (2009)
a service of Schloss Dagstuhl - Leibniz Center for Informatics