Worst-Case Running Times for Average-Case Algorithms

by L. Antunes and L. Fortnow

Oded's comments

This work builds on an earlier work of the authors and Vinodchandran (2003), who showed that the exact (i.e., pointwise) complexity of a problem (or rather any pointwise behavior of an algorithm) that is polynomial on the average w.r.t a certain distribution is characterized by a function related to that distribution. Specifically, both the distribution and the pointwise bound are determined by the polynomial-time Kolmogorov distribution.
The current work goes beyond the previous one by proving that, under standard assumptions that allow derandomization, the class of polynomial-time Kolmogorov distribution is "universal" for the class of P-samplable distributions. Here universality means that the latter distributions dominate all P-samplable distributions, which seems to be of independent interest.
[To appear in CCC'09.]

The original abstract

Under a standard hardness assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all polynomial-time samplable distributions. More precisely we show that if exponential time is not infinitely often in subexponential space, then the following are equivalent for any algorithm $A$: where $K(x)$ is the Kolmogorov complexity (size of smallest program generating $x$) and $K^p(x)$ is the size of the smallest program generating $x$ within time $p(|x|)$.
To prove this result we show that, under the hardness assumption, the polynomial-time Kolmogorov distribution, $m^p(x)=2^{-K^p(x)}$, is universal among the P-samplable distributions.

Back to list of Oded's choices.