Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-144 | 5th December 2005 00:00

Time-Bounded Universal Distributions

RSS-Feed




TR05-144
Authors: Lance Fortnow, Luis Antunes
Publication: 6th December 2005 10:16
Downloads: 2752
Keywords: 


Abstract:

We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions.



ISSN 1433-8092 | Imprint