Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto

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 >>>

Shuichi Hirahara

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 >>>