 Authors: A. Antunes, L. Fortnow, D. van Melkebeek, and N. Vinodchandran.
 Reference: Theoretical Computer Science, 354: 391404, 2006.
Special issue of for selected papers from
the 14th International Symposium on Fundamentals of Computation Theory.
 Earlier version:
 A. Antunes, L. Fortnow, and D. van Melkebeek.
Computational Depth.
In
Proceedings of the 16th IEEE Conference on Computational
Complexity, pages 266273, 2001.
Abstract
We introduce Computational Depth, a measure for the amount of
"nonrandom" or "useful" information in a string by considering the
difference of various Kolmogorov complexity measures. We investigate
three instantiations of Computational Depth:

Basic Computational Depth, a clean notion capturing the
spirit of Bennett's Logical Depth. We show that a Turing machine
M runs in time polynomial on average over the timebounded
universal distribution if and only if for all inputs x, M uses
time exponential in the basic computational depth of x.

Sublineartime Computational Depth and the resulting concept of
Shallow Sets,
a generalization of sparse and random sets based on low depth properties
of their characteristic sequences. We show that every computable set
that is reducible to a shallow set has polynomialsize circuits.

Distinguishing Computational Depth, measuring when strings are
easier to recognize than to produce. We show that if a Boolean formula
has a nonnegligible fraction of its satisfying assignments with low
depth, then we can find a satisfying assignment efficiently.