We develop a measure of "useful information" that we call computational depth as the difference of two different Kolmogorov complexity measures. We believe our measure is simpler and cleaner than previous definitions. We also get many interesting applications, including:
- We show that if a Boolean formula has satisfying assignments mostly of low depth, than we can find these witnesses quickly.
- We develop a notion of shallow sets that generalizes sparse and random sets, and show that any computable set reducible to a shallow set has small circuits.
- We show that an algorithm is polynomial-time on average for all "reasonable" distributions if and only for all inputs x, the algorithm runs in time exponential in the depth of x.
- We explore definitions of "sophistication", the deepest of all strings and show they exist and encode the halting problem.

This work is based on the two papers below and some additional unpublished work.
L. Antunes, L. Fortnow, and D. van Melkebeek. Computational depth. In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 266-273. IEEE, New York, 2001.

L. Antunes, L. Fortnow, and V. Vinodchandran. Computational depth vs. average polynomial time. Technical Report 2001-097, NEC Research Institute, 2001.

Both of these papers are available at http://www.neci.nj.nec.com/homepages/fortnow/papers