Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Luis Antunes:

TR06-125 | 20th September 2006
Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto

Low-Depth Witnesses are Easy to Find

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the
notion of non-random information by computational depth, the
difference between the polynomial-time-bounded Kolmogorov
complexity and traditional Kolmogorov complexity We show how to
find satisfying assignments for formulas that have at least one
assignment of logarithmic depth. The converse holds under a
standard ... more >>>

TR05-144 | 5th December 2005
Lance Fortnow, Luis Antunes

Time-Bounded Universal Distributions

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.

more >>>

ISSN 1433-8092 | Imprint