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.
This is a joint work with Lance Fortnow.