## 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$:
- For all $\p$-samplable distributions $\mu$, $A$ runs in time
polynomial on $\mu$-average.
- For all polynomial $p$, the running time for A is bounded by
$2^{O(K^p(x)-K(x)+\log(|x|))}$ for \emph{all} inputs $x$.

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.