| [1] |
P. Albert, E. Mayordomo, and P. Moser. Bounded pushdown dimension vs Lempel Ziv information density. Technical Report 0704.2386, 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] |
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 ] |
| [5] |
R. Beigel, L. Fortnow, and F. Stephan. Infinitely-often autoreducible sets. SIAM Journal on Computing, 36(3):595-608, 2006. [ PostScript | PDF ] |
| [6] |
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 ] |
| [7] |
L. Bienvenu, D. Doty, and F. Stephan. Constructive dimension and weak truth-table degrees. In Proceedings of the Third Conference on Computability in Europe, pages 63-72. Springer-Verlag, 2007. [ PostScript | PDF ] |
| [8] |
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 ] |
| [9] |
C. Bourke. Finite-state dimension of individual sequences. Master's thesis, University of Nebraska-Lincoln, 2004. [ PostScript | PDF ] |
| [10] |
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 ] |
| [11] |
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 ] |
| [12] |
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 ] |
| [13] |
D. Doty. Dimension extractors and optimal decompression. Theory of Computing Systems. To appear. [ PostScript | PDF ] |
| [14] |
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 | PostScript | PDF ] |
| [15] |
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 ] |
| [16] |
D. Doty, J. H. Lutz, and S. Nandakumar. Finite-state dimension and real arithmetic. Information and Computation, 205(11):1640-1651, 2007. [ PostScript | PDF ] |
| [17] |
D. Doty and P. Moser. Finite-state dimension and lossy decompressors. Technical Report cs.CC/0609096, Computing Research Repository, 2006. [ Abstract | PostScript | PDF ] |
| [18] |
D. Doty and J. Nichols. Pushdown dimension. Theoretical Computer Science, 381(1-3):105-123, 2007. [ DOI | PostScript | PDF ] |
| [19] |
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 ] |
| [20] |
R. Downey and N. Greenberg. Turing degrees of reals of positive effect packing dimension. Manuscript, 2007. [ PDF ] |
| [21] |
R. Downey and D. Hirschfeldt. Algorithmic Randomness and Complexity. Book draft, 2007. To be published by Springer-Verlag. [ PostScript | PDF ] |
| [22] |
R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn. Calibrating randomness. Bulletin of Symbolic Logic, 12(3):411-491, 2006. [ PostScript | PDF ] |
| [23] |
R. Downey, W. Merkle, and J. Reimann. Schnorr dimension. Mathematical Structures in Computer Science, 16(5):789-811, 2006. [ DOI | PDF ] |
| [24] |
S. A. Fenner. Gales and supergales are equivalent for defining constructive Hausdorff dimension. Technical Report cs.CC/0208044, Computing Research Repository, 2002. [ Abstract | PostScript | PDF ] |
| [25] |
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 ] |
| [26] |
L. Fortnow and J. H. Lutz. Prediction and dimension. Journal of Computer and System Sciences, 70(4):570-589, 2005. [ DOI | PostScript ] |
| [27] |
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 ] |
| [28] |
X. Gu. A note on dimensions of polynomial size circuits. Theoretical Computer Science, 359(1-3):176-187, 2006. [ DOI | Abstract | PostScript | PDF ] |
| [29] |
X. Gu and J. H. Lutz. Dimension characterizations of complexity classes. Computational Complexity. To appear. [ PDF ] |
| [30] |
X. Gu and J. H. Lutz. Effective dimensions and relative frequencies. In Proceedings of the Fourth Conference on Computability in Europe. Springer-Verlag, 2008. To appear. [ PDF ] |
| [31] |
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 ] |
| [32] |
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 ] |
| [33] |
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. [ Abstract | PostScript | PDF ] |
| [34] |
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 ] |
| [35] |
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 ] |
| [36] |
J. M. Hitchcock. Effective Fractal Dimension: Foundations and Applications. PhD thesis, Iowa State University, 2003. [ Abstract | PostScript | PDF ] |
| [37] |
J. M. Hitchcock. Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science, 304(1-3):431-441, 2003. [ DOI | Abstract | PostScript | PDF ] |
| [38] |
J. M. Hitchcock. Gales suffice for constructive dimension. Information Processing Letters, 86(1):9-12, 2003. [ DOI | Abstract | PostScript | PDF ] |
| [39] |
J. M. Hitchcock. Small spans in scaled dimension. SIAM Journal on Computing, 34(1):170-194, 2004. [ DOI | Abstract | PostScript | PDF ] |
| [40] |
J. M. Hitchcock. Correspondence principles for effective dimensions. Theory of Computing Systems, 38(5):559-571, 2005. [ DOI | Abstract | PostScript | PDF ] |
| [41] |
J. M. Hitchcock. Hausdorff dimension and oracle constructions. Theoretical Computer Science, 355(3):382-388, 2006. [ DOI | Abstract | PostScript | PDF ] |
| [42] |
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 ] |
| [43] |
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. To appear. [ Abstract | PostScript | PDF ] |
| [44] |
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 ] |
| [45] |
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 ] |
| [46] |
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 ] |
| [47] |
J. M. Hitchcock and A. Pavan. Hardness hypotheses, derandomization, and circuit complexity. Computational Complexity. To appear. [ Abstract | PostScript | PDF ] |
| [48] |
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 ] |
| [49] |
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 ] |
| [50] |
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 ] |
| [51] |
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 ] |
| [52] |
M. López-Valdés. Scaled dimension of individual strings. Technical Report TR06-047, Electronic Colloquium on Computational Complexity, 2006. [ Abstract | PostScript | PDF ] |
| [53] |
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 ] |
| [54] |
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 [56]. |
| [55] |
J. H. Lutz. Dimension in complexity classes. SIAM Journal on Computing, 32(5):1236-1259, 2003. [ DOI | PostScript ] |
| [56] |
J. H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187(1):49-79, 2003. [ DOI | PostScript ] |
| [57] |
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 ] |
| [58] |
J. H. Lutz. Effective fractal dimensions. Mathematical Logic Quarterly, 51:62-72, 2005. [ DOI | PostScript ] |
| [59] |
J. H. Lutz and E. Mayordomo. Dimensions of points in self-similar fractals. Manuscript, 2006. [ PDF ] |
| [60] |
J. H. Lutz and K. Weihrauch. Connectivity properties of dimension level sets. Mathematical Logic Quarterly. To appear. [ PDF ] |
| [61] |
E. Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Information Processing Letters, 84(1):1-3, 2002. [ DOI | PostScript (gzipped) ] |
| [62] |
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) ] |
| [63] |
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 ] |
| [64] |
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 ] |
| [65] |
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 ] |
| [66] |
J. S. Miller and A. Nies. Randomness and computability: open questions. Bulletin of Symbolic Logic, 12(3):390-410, 2006. [ PostScript | PDF ] |
| [67] |
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 ] |
| [68] |
P. Moser. Derandomization and Quantitative Complexity. PhD thesis, Université de Genève, 2004. [ PostScript ] |
| [69] |
P. Moser. Martingale families and dimension in P. In Proceedings of Second Conference on Computability in Europe, pages 388-397. Springer-Verlag, 2006. [ DOI | PostScript ] |
| [70] |
P. Moser. Generic density and small span theorem. Information and Computation, 206(1):1-14, 2008. [ DOI | PDF ] |
| [71] |
S. Nandakumar. A characterization of constructive dimension. In Proceedings of the Fourth International Conference on Computability and Complexity in Analysis. Springer-Verlag, 2007. To appear. [ PDF ] |
| [72] |
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 ] |
| [73] |
S. Reid. The classes of algorithmically random reals. Master's thesis, Victoria University of Wellington, 2003. [ PostScript ] |
| [74] |
J. Reimann. Computability and fractal dimension. PhD thesis, Ruprecht-Karls Universität Heidelberg, 2004. [ PDF ] |
| [75] |
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 ] |
| [76] |
L. Staiger. Constructive dimension equals Kolmogorov complexity. Information Processing Letters, 93(3):149-153, 2005. [ DOI | PDF ] |
| [77] |
F. Stephan. Hausdorff-dimension and weak truth-table reducibility. Technical Report TR52/05, School of Computing, National University of Singapore, 2005. [ PostScript ] |
| [78] |
S. A. Terwijn. Complexity and randomness. Rendiconti del Seminario Matematico di Torino, 62(1):1-38, 2004. [ PostScript ] |
| [79] |
M. Zimand. Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. Technical Report 0705.4658, Computing Research Repository, 2007. [ Abstract | PostScript | PDF ] |
This file has been generated by bibtex2html 1.76