| [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
UWYO Essay service topgradeessay.com