Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMPUTATIONAL DEPTH:
Reports tagged with Computational Depth:
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 >>>


TR21-058 | 21st April 2021
Shuichi Hirahara

Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this ... more >>>




ISSN 1433-8092 | Imprint