Worst-Case Running Times for Average-Case Algorithms

• Type: Article in International Conference Proceedings Book
• Date: 2009

Authors

antunes, l (Author) FCUP; fortnow, l (Author) Other

Conference proceedings International

Title: PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY

Pages: 298-+

24th Annual IEEE Conference on Computational Complexity

Paris, FRANCE, JUL 15-18, 2009

Indexing

ISI Web of Knowledge - 13 Citations

Scopus - 24 Citations

Other information

Authenticus ID: P-003-RRV

DOI: 10.1109/ccc.2009.12

Abstract (EN): 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(Kp(x)-K(x)+log(|x|))) for 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(-Kp(x)), is universal among the P-samplable distributions.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 3