When Average Case is the Worst Case

Birthday Boy Rocco Servedio gave a talk at TTI on Friday on learning random functions over random inputs. John Langford asked about distributions that put more weight on simpler string, those of lower Kolmogorov complexity. That reminded me of a nifty 1992 result of Ming Li and Paul Vitányi.

Fix your favorite programming language and let K(x) be the length of the smallest program generating string x. Define μ(x)=2^-K(x), known as the universal distribution for reasons I won't get into here. Notice how strings of smaller complexity get more weight.

Theorem (Li-Vitányi) Any algorithm using time T(n) on average over the universal distribution uses time O(T(n)) in the worst case.

Li and Vitányi prove their theorem by showing that if the set of worst-case inputs is small they will have a short description and thus more heavily weighted under μ. Read all the details in their paper.