29 references, page 1 of 3 [1] Krishna Athreya, John Hitchcock, Jack H. Lutz and Elvira Mayordomo. Effective strong dimension, algorithmic information and computational complexity. SIAM Journal on Computing, 37:671-705, 2007.

[2] Laurent Bienvenu, David Doty, and Frank Stephan. Constructive Dimension and Weak Truth-Table Degrees. in S. Barry Cooper, Benedikt Lo¨we, and Andrea Sorbi (editors), Computation and Logic in the Real World - Third Conference of Computability in Europe (CiE 2007), (Siena, Italy, June 18-23, 2007), Proceedings, Lecture Notes in Computer Science, volume 4497, Spring-Verlag, 2007, pp. 63-72.

[3] Cristian S. Calude and Gregory J. Chaitin. Randomness everywhere. Nature, 400:319- 320, 1999.

[4] David Doty. Every sequence is decompressible from a random one. In Logical Approaches to Computational Barriers, Proceedings of the Second Conference on Computability in Europe, Springer Lecture Notes in Computer Science, volume 3988 of Computability in Europe, Swansea, UK, July 2006, pp. 153-162.

[5] David Doty. Dimension extractors and optimal decompression. Theory of Computing Systems, 43(3-4):425-463, 2008. Special issue of selected papers from Computability in Europe 2006.

[6] Lance Fortnow, John M. Hitchcock, Pavan Aduri, N. Variyam Vinodchandran and Fengming Wang. Extracting Kolmogorov complexity with applications to dimension zero-one laws. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Springer LNCS, 4051:335-345, 2006.

[7] Richard Friedberg and Hartley Rogers. Reducibilities and completeness for sets of integers. Zeitschrift fu¨r Mathematische Logik und Grundlagen der Mathematik, 5:117-125, 1959.

[8] Felix Hausdorff. Dimension und ¨ausseres Mass. Mathematische Annalen, 79:157-179, 1919.

[9] Lane Hemaspaandra, Harald Hempel and J¨org Vogel. Optimal Separations for Parallel versus Sequential Self-Checking: Parallelism Can Exponentially Increase Self-Checking Cost. Technical Report TR 691, Department of Computer Science, University of Rochester, May 1998.

[10] Ming Li and Paul M. B. Vit´anyi. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, Berlin, 1997. Second Edition.