Effective Fractal Dimension Bibliography

Maintained by John Hitchcock. Also available in PostScript and PDF.

[1] P. Albert, E. Mayordomo, and P. Moser.
Bounded pushdown dimension vs Lempel Ziv information density.
Technical Report arXiv:0704.2386 [cs.CC], Computing Research Repository, 2007.
[ Abstract | PostScript | PDF ]

[2] P. Albert, E. Mayordomo, P. Moser, and S. Perifel.
Pushdown compression.
In Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, pages 39-48.
Springer-Verlag, 2008.
[ Abstract | PostScript | PDF ]

[3] K. Ambos-Spies, W. Merkle, J. Reimann, and F. Stephan.
Hausdorff dimension in exponential time.
In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 210-217.
IEEE Computer Society, 2001.
[ DOI | PostScript ]

[4] L. Antunes, A. Matos, A. Souto, and P. Vit'anyi.
Depth as randomness deficiency.
Theory of Computing Systems, 45(4):724-739, 2009.
[ DOI | PDF ]

[5] L. Antunes and A. Souto.
Sophisticated infinite sequences.
In Proceedings of the Fourth Conference on Computability in Europe, pages 25-34, 2008.
[ PDF ]

[6] K. B. Athreya, J. M. Hitchcock, J. H. Lutz, and E. Mayordomo.
Effective strong dimension in algorithmic information and computational complexity.
SIAM Journal on Computing, 37(3):671-705, 2007.
[ DOI | Abstract | PostScript | PDF ]

[7] R. Beigel, L. Fortnow, and F. Stephan.
Infinitely-often autoreducible sets.
SIAM Journal on Computing, 36(3):595-608, 2006.
[ PostScript | PDF ]

[8] L. Bienvenu.
Kolmogorov-Loveland stochasticity and Kolmogorov complexity.
In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science, pages 260-271.
Springer-Verlag, 2007.
[ PDF ]

[9] L. Bienvenu.
Caractérisations de l'aléatoire par les jeux: imprédictibilité et stochasticité.
PhD thesis, Université de Provence, 2008.
[ PDF ]

[10] L. Bienvenu, D. Doty, and F. Stephan.
Constructive dimension and Turing degrees.
Theory of Computing Systems, 45(4):740-755, 2009.
[ Abstract | DOI | PostScript | PDF ]

[11] L. Bienvenu and W. Merkle.
Reconciling data compression and Kolmogorov complexity.
In Proceedings of the 34th International Colloquium on Automata, Languages, and Programming, pages 643-654.
Springer-Verlag, 2007.
[ PDF ]

[12] C. Bourke.
Finite-state dimension of individual sequences.
Master's thesis, University of Nebraska-Lincoln, 2004.
[ PDF | PostScript ]

[13] C. Bourke, J. M. Hitchcock, and N. V. Vinodchandran.
Entropy rates and finite-state dimension.
Theoretical Computer Science, 349(3):392-406, 2005.
[ DOI | Abstract | PostScript | PDF ]

[14] C. S. Calude, L. Staiger, and S. A. Terwijn.
On partial randomness.
Annals of Pure and Applied Logic, 138(1-3):20-30, 2006.
[ DOI | PDF ]

[15] C. S. Calude and M. Zimand.
Algorithmically independent sequences.
In Proceedings of the Twelfth International Conference on Developments In Language Theory.
Springer-Verlag, 2008. To appear.
[ DOI | PDF ]

[16] C. J. Conidis.
Effective Packing Dimension Of Π01-Classes.
Proceedings of the American Mathematical Society, 136(10):3655-3662, 2008.
[ DOI | PDF ]

[17] C. J. Conidis.
Applications of computability theory.
PhD thesis, University of Chicago, 2009.
[ PDF ]

[18] J. J. Dai, J. I. Lathrop, J. H. Lutz, and E. Mayordomo.
Finite-state dimension.
Theoretical Computer Science, 310(1-3):1-33, 2004.
[ DOI | PostScript ]

[19] D. Diamondstone and B. Kjos-Hanssen.
Members of random closed sets.
In Proceedings of the 5th Conference on Computability in Europe, pages 144-153, 2009.
[ DOI ]

[20] D. Doty.
Every sequence is decompressible from a random one.
In Proceedings of the Second Conference on Computability in Europe, pages 153-162.
Springer-Verlag, 2006.
[ DOI | Abstract | PostScript | PDF ]

[21] D. Doty.
Dimension extractors and optimal decompression.
Theory of Computing Systems, 43(3-4):425-463, 2008.
[ DOI | Abstract | PostScript | PDF ]

[22] D. Doty, X. Gu, J. H. Lutz, E. Mayordomo, and P. Moser.
Zeta-dimension.
In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, pages 283-294.
Springer-Verlag, 2005.
[ DOI | Abstract | PostScript | PDF ]

[23] D. Doty, J. H. Lutz, and S. Nandakumar.
Finite-state dimension and real arithmetic.
Information and Computation, 205(11):1640-1651, 2007.
[ DOI | Abstract | PostScript | PDF ]

[24] D. Doty and P. Moser.
Finite-state dimension and lossy decompressors.
Technical Report arXiv:cs/0609096 [cs.CC], Computing Research Repository, 2006.
[ Abstract | PostScript | PDF ]

[25] D. Doty and J. Nichols.
Pushdown dimension.
Theoretical Computer Science, 381(1-3):105-123, 2007.
[ DOI | Abstract | PostScript | PDF ]

[26] R. Downey.
Some recent progress in algorithmic randomness.
In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science, pages 42-83.
Springer-Verlag, 2004.
[ PostScript ]

[27] R. Downey.
Algorithmic randomness and computability.
Manuscript, 2009.
[ PDF ]

[28] R. Downey and N. Greenberg.
Turing degrees of reals of positive effect packing dimension.
Information Processing Letters, 108(5):298-303, 2008.
[ DOI | PostScript (gzipped) | PDF ]

[29] R. Downey and D. Hirschfeldt.
Algorithmic Randomness and Complexity.
Springer-Verlag. To appear.
[ PostScript | PDF ]

[30] R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn.
Calibrating randomness.
Bulletin of Symbolic Logic, 12(3):411-491, 2006.
[ PostScript | PDF ]

[31] R. Downey, W. Merkle, and J. Reimann.
Schnorr dimension.
Mathematical Structures in Computer Science, 16(5):789-811, 2006.
[ DOI | PDF ]

[32] R. Downey and K. M. Ng.
Effective packing dimension and traceability.
Notre Dame Journal of Formal Logic. To appear.
[ PDF ]

[33] S. A. Fenner.
Gales and supergales are equivalent for defining constructive Hausdorff dimension.
Technical Report arXiv:cs/0208044 [cs.CC], Computing Research Repository, 2002.
[ Abstract | PostScript | PDF ]

[34] L. Fortnow, J. M. Hitchcock, A. Pavan, N. V. Vinodchandran, and F. Wang.
Extracting Kolmogorov complexity with applications to dimension zero-one laws.
In Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming, pages 335-345.
Springer-Verlag, 2006.
[ DOI | Abstract | PostScript | PDF ]

[35] L. Fortnow and J. H. Lutz.
Prediction and dimension.
Journal of Computer and System Sciences, 70(4):570-589, 2005.
[ DOI | PostScript ]

[36] C. Glaßer, M. Ogihara, A. Pavan, A. Selman, and L. Zhang.
Autoreducibility, mitoticity, and immunity.
Technical Report TR05-011, Electronic Colloquium on Computational Complexity, 2005.
[ Abstract | PostScript | PDF ]

[37] N. Greenber and J. S. Miller.
Diagonally non-recursive functions and effective Hausdorff dimension.
Submitted, 2009.
[ PDF ]

[38] X. Gu.
A note on dimensions of polynomial size circuits.
Theoretical Computer Science, 359(1-3):176-187, 2006.
[ DOI | Abstract | PostScript | PDF ]

[39] X. Gu and J. H. Lutz.
Dimension characterizations of complexity classes.
Computational Complexity. To appear.
[ PDF ]

[40] X. Gu and J. H. Lutz.
Effective dimensions and relative frequencies.
In Proceedings of the Fourth Conference on Computability in Europe, pages 231-240.
Springer-Verlag, 2008.
[ DOI | Abstract | PDF ]

[41] X. Gu, J. H. Lutz, and E. Mayordomo.
Points on computable curves.
In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 469-474.
IEEE Computer Society, 2006.
[ Abstract | PostScript | PDF ]

[42] X. Gu, J. H. Lutz, and P. Moser.
Dimensions of Copeland-Erdös sequences.
Information and Computation, 205(9):1317-1333, 2007.
[ DOI | Abstract | PostScript | PDF ]

[43] R. C. Harkins and J. M. Hitchcock.
Dimension, halfspaces, and the density of hard sets.
In Proceedings of the 13th Annual International Computing and Combinatorics Conference, pages 129-139.
Springer-Verlag, 2007.
[ DOI | Abstract | PostScript | PDF ]

[44] M. Hauptmann.
Scaled dimension and the Berman-Hartmanis conjecture.
Technical Report 85300-CS, University of Bonn, 2008.
[ Abstract | PostScript (gzipped) ]

[45] D. R. Hirschfeldt and S. A. Terwijn.
Limit computability and constructive measure.
In Proceedings of IMS Workshop on Computational Prospects of Infinity. To appear.
[ Abstract | PostScript | PDF ]

[46] J. M. Hitchcock.
MAX3SAT is exponentially hard to approximate if NP has positive dimension.
Theoretical Computer Science, 289(1):861-869, 2002.
[ DOI | Abstract | PostScript | PDF ]

[47] J. M. Hitchcock.
Effective Fractal Dimension: Foundations and Applications.
PhD thesis, Iowa State University, 2003.
[ Abstract | PostScript | PDF ]

[48] J. M. Hitchcock.
Fractal dimension and logarithmic loss unpredictability.
Theoretical Computer Science, 304(1-3):431-441, 2003.
[ DOI | Abstract | PostScript | PDF ]

[49] J. M. Hitchcock.
Gales suffice for constructive dimension.
Information Processing Letters, 86(1):9-12, 2003.
[ DOI | Abstract | PostScript | PDF ]

[50] J. M. Hitchcock.
Small spans in scaled dimension.
SIAM Journal on Computing, 34(1):170-194, 2004.
[ DOI | Abstract | PostScript | PDF ]

[51] J. M. Hitchcock.
Correspondence principles for effective dimensions.
Theory of Computing Systems, 38(5):559-571, 2005.
[ DOI | Abstract | PostScript | PDF ]

[52] J. M. Hitchcock.
Hausdorff dimension and oracle constructions.
Theoretical Computer Science, 355(3):382-388, 2006.
[ DOI | Abstract | PostScript | PDF ]

[53] J. M. Hitchcock.
Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets.
SIAM Journal on Computing, 36(6):1696-1708, 2007.
[ DOI | Abstract | PostScript | PDF ]

[54] J. M. Hitchcock, M. López-Valdés, and E. Mayordomo.
Scaled dimension and the Kolmogorov complexity of Turing-hard sets.
Theory of Computing Systems, 43(3-4):471-497, 2008.
[ DOI | Abstract | PostScript | PDF ]

[55] J. M. Hitchcock, J. H. Lutz, and E. Mayordomo.
Scaled dimension and nonuniform complexity.
Journal of Computer and System Sciences, 69(2):97-122, 2004.
[ DOI | Abstract | PostScript | PDF ]

[56] J. M. Hitchcock, J. H. Lutz, and E. Mayordomo.
The fractal geometry of complexity classes.
SIGACT News, 36(3):24-38, September 2005.
[ DOI | Abstract | PostScript | PDF ]

[57] J. M. Hitchcock, J. H. Lutz, and S. A. Terwijn.
The arithmetical complexity of dimension and randomness.
ACM Transactions on Computational Logic, 8(2):article 13, 2007.
[ DOI | Abstract | PostScript | PDF ]

[58] J. M. Hitchcock and A. Pavan.
Resource-bounded strong dimension versus resource-bounded category.
Information Processing Letters, 95(3):377-381, 2005.
[ DOI | Abstract | PostScript | PDF ]

[59] J. M. Hitchcock and A. Pavan.
Hardness hypotheses, derandomization, and circuit complexity.
Computational Complexity, 17(1):119-146, 2008.
[ DOI | Abstract | PostScript | PDF ]

[60] J. M. Hitchcock, A. Pavan, and N. V. Vinodchandran.
Partial bi-immunity, scaled dimension, and NP-completeness.
Theory of Computing Systems, 42(2):131-142, 2008.
[ DOI | Abstract | PostScript | PDF ]

[61] J. M. Hitchcock and N. V. Vinodchandran.
Dimension, entropy rates, and compression.
Journal of Computer and System Sciences, 72(4):760-782, 2006.
[ DOI | Abstract | PostScript | PDF ]

[62] B. Kjos-Hanssen.
Infinite subsets of random sets of integers.
Manuscript, 2008.
[ PDF ]

[63] B. Kjos-Hanssen and A. Nerode.
Effective dimension of points visited by brownian motion.
Theoretical Computer Science, 410(4-5):347-354, 2008.
[ DOI | PDF ]

[64] V. Kreinovich and L. Longpré.
Kolmogorov complexity leads to a representation theorem for idempotent probabilities (σ-maxitive measures).
SIGACT News, 36(3):107-112, September 2005.
[ DOI ]

[65] M. López-Valdés.
Lempel-Ziv dimension for Lempel-Ziv compression.
In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, pages 693-703.
Springer-Verlag, 2006.
[ DOI | Abstract | PostScript | PDF ]

[66] M. López-Valdés.
Scaled dimension of individual strings.
Technical Report TR06-047, Electronic Colloquium on Computational Complexity, 2006.
[ Abstract | PostScript | PDF ]

[67] M. López-Valdés and E. Mayordomo.
Dimension is compression.
In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, pages 676-685.
Springer-Verlag, 2005.
[ DOI | PDF ]

[68] J. H. Lutz.
Gales and the constructive dimension of individual sequences.
In Proceedings of the 27th International Colloquium on Automata, Languages, and Programming, pages 902-913.
Springer-Verlag, 2000.
Revised as [70].
[ DOI ]

[69] J. H. Lutz.
Dimension in complexity classes.
SIAM Journal on Computing, 32(5):1236-1259, 2003.
[ DOI | Abstract | PostScript ]

[70] J. H. Lutz.
The dimensions of individual strings and sequences.
Information and Computation, 187(1):49-79, 2003.
[ DOI | Abstract | PostScript ]

[71] J. H. Lutz.
The dimension of a point: Computability meets fractal geometry.
In Proceedings of New Computational Paradigms: First Conference on Computability in Europe, page 299.
Springer-Verlag, 2005.
[ DOI ]

[72] J. H. Lutz.
Effective fractal dimensions.
Mathematical Logic Quarterly, 51:62-72, 2005.
[ DOI | PostScript ]

[73] J. H. Lutz.
A divergence formula for randomness and dimension.
In Proceedings of the 5th Conference on Computability in Europe, 2009.
[ DOI | Abstract | PostScript | PDF ]

[74] J. H. Lutz and E. Mayordomo.
Dimensions of points in self-similar fractals.
SIAM Journal on Computing, 38:1080-1112, 2008.
[ PDF ]

[75] J. H. Lutz and K. Weihrauch.
Connectivity properties of dimension level sets.
Mathematical Logic Quarterly, 54(5):483-491, 2008.
[ DOI | PDF ]

[76] E. Mayordomo.
A Kolmogorov complexity characterization of constructive Hausdorff dimension.
Information Processing Letters, 84(1):1-3, 2002.
[ DOI | PostScript (gzipped) ]

[77] E. Mayordomo.
Effective Hausdorff dimension.
In B. Löwe, B. Piwinger, and T. Räsch, editors,
Classical and New Paradigms of Computation and their Complexity Hierarchies, volume 23 of Trends in Logic, pages 171-186.
Kluwer Academic Press, 2004.
[ PostScript (gzipped) ]

[78] E. Mayordomo.
Two open problems on effective dimension.
In Proceedings of Second Conference on Computability in Europe, pages 353-359.
Springer-Verlag, 2006.
[ DOI | PDF ]

[79] E. Mayordomo.
Effective fractal dimension in algorithmic information theory.
In S. B. Cooper, B. Löwe, and A. Sorbi, editors,
New Computational Paradigms: Changing Conceptions of What is Computable, pages 259-285.
Springer-Verlag, 2008.
[ PDF ]

[80] W. Merkle, J. S. Miller, A. Nies, J. Reimann, and F. Stephan.
Kolmogorov-Loveland randomness and stochasticity.
Annals of Pure and Applied Logic, 138(1-3):183-210, 2006.
[ DOI | PDF ]

[81] J. S. Miller.
Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension.
Advances in Mathematics. To appear.
[ PDF ]

[82] J. S. Miller and A. Nies.
Randomness and computability: open questions.
Bulletin of Symbolic Logic, 12(3):390-410, 2006.
[ PostScript | PDF ]

[83] P. Moser.
BPP has effective dimension at most 1/2 unless BPP = EXP.
Technical Report TR03-029, Electronic Colloquium on Computational Complexity, 2003.
[ Abstract | PostScript | PDF ]

[84] P. Moser.
Derandomization and Quantitative Complexity.
PhD thesis, Université de Genève, 2004.
[ PostScript ]

[85] P. Moser.
Generic density and small span theorem.
Information and Computation, 206(1):1-14, 2008.
[ DOI | PDF ]

[86] P. Moser.
Martingale families and dimension in P.
Theoretical Computer Science, 400(1-3):46-61, 2008.
[ DOI | PostScript ]

[87] S. Nandakumar.
A characterization of constructive dimension.
In Proceedings of the Fourth International Conference on Computability and Complexity in Analysis, pages 323-337, 2008.
[ PDF ]

[88] K. M. Ng.
Computability, Traceability and Beyond.
PhD thesis, Victoria University of Wellington, 2009.
[ PDF ]

[89] A. Nies and J. Reimann.
A lower cone in the wtt degrees of non-integral effective dimension.
In Proceedings of IMS Workshop on Computational Prospects of Infinity. To appear.
[ PDF ]

[90] S. Reid.
The classes of algorithmically random reals.
Master's thesis, Victoria University of Wellington, 2003.
[ PostScript ]

[91] J. Reimann.
Randomness beyond Lebesgue measure.
In Proceedings of Logic Colloquium 06. To appear.
[ PDF ]

[92] J. Reimann.
Computability and fractal dimension.
PhD thesis, Ruprecht-Karls Universität Heidelberg, 2004.
[ PDF ]

[93] J. Reimann.
Effectively closed sets of measures and randomness.
Annals of Pure and Applied Logic, 156:170-182, 2008.
[ DOI | DOI | PDF ]

[94] J. Reimann and F. Stephan.
Effective Hausdorff dimension.
In M. Baaz, S. D. Friedman, and J. Krajícek, editors,
Logic Colloquium '01, volume 20 of Lecture Notes in Logic, pages 369-385.
Association for Symbolic Logic, 2005.
[ PDF ]

[95] J. Reimann and F. Stephan.
Hierarchies of randomness tests.
In Proceedings of the 9th Asian Logic Conference. World Scientific Publishing, 2006.
[ PDF ]

[96] L. Staiger.
Constructive dimension equals Kolmogorov complexity.
Information Processing Letters, 93(3):149-153, 2005.
[ DOI | PDF ]

[97] F. Stephan.
Hausdorff-dimension and weak truth-table reducibility.
In D. Zambella K. Kearnes, A. Andretta, editor, Logic Colloquium 2004, volume 29 of Lecture Notes in Logic, pages 157-167.
Association for Symbolic Logic, 2008.
[ PostScript ]

[98] K. Tadaki.
Partial randomness and dimension of recursively enumerable reals.
In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science, pages 687-699, 2009.
[ DOI ]

[99] S. A. Terwijn.
Complexity and randomness.
Rendiconti del Seminario Matematico di Torino, 62(1):1-38, 2004.
[ PostScript | PDF ]

[100] D. Turetsky.
Connectedness properties of dimension level sets.
Manuscript, 2009.
[ PDF ]

[101] F. Wang.
Kolmogorov extraction and resource-bounded zero-one laws.
Master's thesis, Iowa State University, 2006.
[ PDF ]

[102] M. Zimand.
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences.
Technical Report arXiv:0705.4658 [cs.IT], Computing Research Repository, 2007.
[ Abstract | PostScript | PDF ]


This file has been generated by bibtex2html 1.76