| [1] |
A. Abey. A correspondence principle for finite-state dimension. Master's thesis, Iowa State University, Ames, IA, USA, 2004. [ DOI | Abstract ] |
| [2] |
M. Agrawal, D. Chakraborty, D. Das, and S. Nandakumar. Dimension, pseudorandomness and extraction of pseudorandomness. Computability, 6(3):277--305, 2017. [ DOI ] |
| [3] |
P. Albert, E. Mayordomo, and P. Moser. Bounded pushdown dimension vs Lempel Ziv information density. In A. Day, M. Fellows, N. Greenberg, B. Khoussainov, A. Melnikov, and F. Rosamond, editors, Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pages 95--114. Springer International Publishing, 2017. [ DOI ] |
| [4] |
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. [ DOI | arXiv ] |
| [5] |
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 ] |
| [6] |
L. Antunes, A. Matos, A. Souto, and P. Vitányi. Depth as randomness deficiency. Theory of Computing Systems, 45(4):724--739, 2009. [ DOI | arXiv ] |
| [7] |
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 | arXiv | Abstract | PDF ] |
| [8] |
M. Bachan. Finite-state dimension of the Kolakoski sequence. Master's thesis, Iowa State University, Ames, IA, USA, 2005. [ Abstract ] |
| [9] |
G. Barmpalias and A. Shen. The Kučera--Gács theorem revisited by Levín. Theoretical Computer Science, 947:113693, 2023. [ DOI ] |
| [10] |
V. Becher, J. Reimann, and T. A. Slaman. Irrationality exponent, hausdorff dimension and effectivization. Monatshefte für Mathematik, 185:167--188, 2018. |
| [11] |
R. Beigel, L. Fortnow, and F. Stephan. Infinitely-often autoreducible sets. SIAM Journal on Computing, 36(3):595--608, 2006. [ DOI ] |
| [12] |
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. [ DOI ] |
| [13] |
L. Bienvenu. Caractérisations de l'aléatoire par les jeux: imprédictibilité et stochasticité. PhD thesis, Université de Provence, 2008. [ PDF ] |
| [14] |
L. Bienvenu, D. Doty, and F. Stephan. Constructive dimension and Turing degrees. Theory of Computing Systems, 45(4):740--755, 2009. [ DOI | arXiv ] |
| [15] |
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 ] |
| [16] |
C. Bourke. Finite-state dimension of individual sequences. Master's thesis, University of Nebraska-Lincoln, 2004. [ PDF ] |
| [17] |
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 | PDF ] |
| [18] |
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 ] |
| [19] |
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 ] |
| [20] |
W. Calvert, E. Gruner, E. Mayordomo, D. Turetsky, and J. D. Villano. Normality, relativization, and randomness. Preprint 2312.10204v2, arXiv, February 2025. [ arXiv ] |
| [21] |
A. Case. Bounded Turing reductions and data processing inequalities for sequences. Theory of Computing Systems, 62(7):1586--1598, 2018. [ DOI | arXiv ] |
| [22] |
A. Case and J. H. Lutz. Mutual dimension. ACM Transactions on Computation Theory (TOCT), 7(3):1--26, 2015. [ DOI | arXiv ] |
| [23] |
A. Case and J. H. Lutz. Mutual dimension and random sequences. Theoretical Computer Science, 731:68--87, 2018. [ DOI | arXiv ] |
| [24] |
A. Case and J. H. Lutz. Finite-state mutual dimension. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing, pages 1--8, 2022. [ DOI ] |
| [25] |
A. Case and C. P. Porter. The intersection of algorithmically random closed sets and effective dimension. ACM Trans. Comput. Log., 23(4):24:1--24:19, 2022. [ DOI | arXiv ] |
| [26] |
A. T. Case. Mutual dimension, data processing inequalities, and randomness. Phd thesis, Iowa State University, 2016. [ Abstract ] |
| [27] |
C. J. Conidis. Effective Packing Dimension Of Π01-Classes. Proceedings of the American Mathematical Society, 136(10):3655--3662, 2008. [ DOI ] |
| [28] |
C. J. Conidis. Applications of computability theory. PhD thesis, University of Chicago, 2009. [ Abstract ] |
| [29] |
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 | PDF ] |
| [30] |
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 ] |
| [31] |
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 | arXiv ] |
| [32] |
D. Doty. Dimension extractors and optimal decompression. Theory of Computing Systems, 43(3--4):425--463, 2008. [ DOI | arXiv ] |
| [33] |
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 | arXiv ] |
| [34] |
D. Doty, J. H. Lutz, and S. Nandakumar. Finite-state dimension and real arithmetic. Information and Computation, 205(11):1640--1651, 2007. [ DOI | arXiv ] |
| [35] |
D. Doty and P. Moser. Finite-state dimension and lossy decompressors. Technical Report arXiv:cs/0609096 [cs.CC], Computing Research Repository, 2006. [ arXiv ] |
| [36] |
D. Doty and J. Nichols. Pushdown dimension. Theoretical Computer Science, 381(1--3):105--123, 2007. [ DOI | arXiv ] |
| [37] |
R. Dougherty, J. Lutz, R. D. Mauldin, and J. Teutsch. Translating the cantor set by a random real. Transactions of the American Mathematical Society, 366(6):3027--3041, 2014. [ Abstract ] |
| [38] |
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. [ DOI ] |
| [39] |
R. Downey. Algorithmic randomness and computability. Manuscript, 2009. [ PDF ] |
| [40] |
R. Downey and N. Greenberg. Turing degrees of reals of positive effective packing dimension. Information Processing Letters, 108(5):298--303, 2008. [ DOI ] |
| [41] |
R. Downey and D. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 2010. [ DOI ] |
| [42] |
R. Downey and D. R. Hirschfeldt. Algorithmic randomness. Communications of the ACM, 62(5):70--80, 4 2019. [ DOI ] |
| [43] |
R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn. Calibrating randomness. Bulletin of Symbolic Logic, 12(3):411--491, 2006. [ DOI ] |
| [44] |
R. Downey, W. Merkle, and J. Reimann. Schnorr dimension. Mathematical Structures in Computer Science, 16(5):789--811, 2006. [ DOI | PDF ] |
| [45] |
R. Downey and K. M. Ng. Effective Packing Dimension and Traceability. Notre Dame Journal of Formal Logic, 51(2):279 -- 290, 2010. [ DOI | DOI ] |
| [46] |
S. A. Fenner. Gales and supergales are equivalent for defining constructive Hausdorff dimension. Technical Report arXiv:cs/0208044 [cs.CC], Computing Research Repository, 2002. [ arXiv | Abstract | PDF ] |
| [47] |
L. Fortnow, J. M. Hitchcock, A. Pavan, N. V. Vinodchandran, and F. Wang. Extracting Kolmogorov complexity with applications to dimension zero-one laws. Information and Computation, 209(4):627--636, 2011. [ DOI | Abstract | PDF ] |
| [48] |
L. Fortnow and J. H. Lutz. Prediction and dimension. Journal of Computer and System Sciences, 70(4):570--589, 2005. [ DOI | PDF ] |
| [49] |
C. Fraize. Aspects of Algorithmically Random Objects. PhD thesis, University of Florida, 2023. [ Abstract ] |
| [50] |
J. N. Y. Franklin and C. P. Porter. Key developments in algorithmic randomness. In J. N. Y. Franklin and C. P. Porter, editors, Algorithmic Randomness: Progress and Prospects, volume 50 of Lecture Notes in Logic, page 1–39. Cambridge University Press, 2020. [ DOI ] |
| [51] |
R. Gavaldà, M. López-Valdés, E. Mayordomo, and N. V. Vinodchandran. Resource-bounded dimension in computational learning theory. Technical report, arXiv, 2010. [ arXiv ] |
| [52] |
N. Greenber and J. S. Miller. Diagonally non-recursive functions and effective Hausdorff dimension. Submitted, 2009. [ PDF ] |
| [53] |
X. Gu. A note on dimensions of polynomial size circuits. Theoretical Computer Science, 359(1--3):176--187, 2006. [ DOI ] |
| [54] |
X. Gu. Fractals in complexity and geometry. PhD thesis, Iowa State University, 2009. [ Abstract ] |
| [55] |
X. Gu and J. H. Lutz. Dimension characterizations of complexity classes. Computational Complexity, 17:459--474, 2008. [ DOI | PDF ] |
| [56] |
X. Gu and J. H. Lutz. Effective dimensions and relative frequencies. Theor. Comput. Sci., 412(48):6696--6711, 2011. [ DOI | arXiv ] |
| [57] |
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. [ arXiv ] |
| [58] |
X. Gu, J. H. Lutz, E. Mayordomo, and P. Moser. Dimension spectra of random subfractals of self-similar fractals. Ann. Pure Appl. Log., 165(11):1707--1726, 2014. [ DOI ] |
| [59] |
X. Gu, J. H. Lutz, and P. Moser. Dimensions of Copeland-Erdös sequences. Information and Computation, 205(9):1317--1333, 2007. [ DOI | PDF ] |
| [60] |
R. C. Harkins and J. M. Hitchcock. Dimension, halfspaces, and the density of hard sets. Theory of Computing Systems, 49(3):601--614, 2011. [ DOI | Abstract | PDF ] |
| [61] |
M. Hauptmann. Scaled dimension and the Berman-Hartmanis conjecture. Technical Report 85300-CS, University of Bonn, 2008. [ Abstract | PDF ] |
| [62] |
D. R. Hirschfeldt and S. A. Terwijn. Limit Computability and Constructive Measure, pages 131--141. World Scientific, 2008. [ DOI ] |
| [63] |
J. M. Hitchcock. Resource-bounded dimension, nonuniform complexity, and approximation of MAX3SAT. Master's thesis, Iowa State University, Ames, IA, USA, 2001. [ DOI | Abstract ] |
| [64] |
J. M. Hitchcock. MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theoretical Computer Science, 289(1):861--869, 2002. [ DOI | Abstract | PDF ] |
| [65] |
J. M. Hitchcock. Effective Fractal Dimension: Foundations and Applications. PhD thesis, Iowa State University, 2003. [ Abstract | PostScript | PDF ] |
| [66] |
J. M. Hitchcock. Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science, 304(1--3):431--441, 2003. [ DOI | Abstract | PDF ] |
| [67] |
J. M. Hitchcock. Gales suffice for constructive dimension. Information Processing Letters, 86(1):9--12, 2003. [ DOI | arXiv | Abstract | PDF ] |
| [68] |
J. M. Hitchcock. Small spans in scaled dimension. SIAM Journal on Computing, 34(1):170--194, 2004. [ DOI | arXiv | Abstract | PDF ] |
| [69] |
J. M. Hitchcock. Correspondence principles for effective dimensions. Theory of Computing Systems, 38(5):559--571, 2005. [ DOI | Abstract | PDF ] |
| [70] |
J. M. Hitchcock. Hausdorff dimension and oracle constructions. Theoretical Computer Science, 355(3):382--388, 2006. [ DOI | Abstract | PDF ] |
| [71] |
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 | arXiv | Abstract | PDF ] |
| [72] |
J. M. Hitchcock. Limitations of efficient reducibility to the Kolmogorov random strings. Computability, 1(1):39--43, 2012. [ DOI | Abstract | PDF ] |
| [73] |
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 | PDF ] |
| [74] |
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 | PDF ] |
| [75] |
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 | PDF ] |
| [76] |
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 | arXiv | Abstract | PDF ] |
| [77] |
J. M. Hitchcock and E. Mayordomo. Base invariance of feasible dimension. Information Processing Letters, 113(14-16):546--551, 2013. [ DOI | Abstract | PDF ] |
| [78] |
J. M. Hitchcock and A. Pavan. Resource-bounded strong dimension versus resource-bounded category. Information Processing Letters, 95(3):377--381, 2005. [ DOI | Abstract | PDF ] |
| [79] |
J. M. Hitchcock and A. Pavan. Hardness hypotheses, derandomization, and circuit complexity. Computational Complexity, 17(1):119--146, 2008. [ DOI | Abstract | PDF ] |
| [80] |
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 | PDF ] |
| [81] |
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 | PDF ] |
| [82] |
X. Huang, J. H. Lutz, E. Mayordomo, and D. M. Stull. Asymptotic divergences and strong dichotomy. IEEE Trans. Inf. Theory, 67(10):6296--6305, 2021. [ DOI | arXiv ] |
| [83] |
L. Jordon. An Investigation of Feasible Logical Depth and Complexity Measures Via Automata and Compression Algorithms. PhD thesis, Maynooth University, 2022. [ Abstract ] |
| [84] |
L. Jordon and P. Moser. On the difference between finite-state and pushdown depth. In A. Chatzigeorgiou, R. Dondi, H. Herodotou, C. A. Kapoutsis, Y. Manolopoulos, G. A. Papadopoulos, and F. Sikora, editors, SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20-24, 2020, Proceedings, volume 12011 of Lecture Notes in Computer Science, pages 187--198. Springer, 2020. [ DOI ] |
| [85] |
B. Kastermans and S. Lempp. Comparing notions of randomness. Theoretical Computer Science, 411(3):602--616, 2010. [ DOI ] |
| [86] |
B. Kjos-Hanssen. Infinite subsets of random sets of integers. Technical report, arXiv, 2014. [ arXiv ] |
| [87] |
B. Kjos-Hanssen and A. Nerode. Effective dimension of points visited by brownian motion. Theoretical Computer Science, 410(4--5):347--354, 2008. [ DOI | arXiv | PDF ] |
| [88] |
A. Kozachinskiy and A. Shen. Two characterizations of finite-state dimension. In Fundamentals of Computation Theory, pages 80--94. Springer International Publishing, 2019. [ DOI ] |
| [89] |
A. Kozachinskiy and A. Shen. Automatic kolmogorov complexity, normality, and finite-state dimension revisited. Journal of Computer and System Sciences, 118:75--107, 2021. [ DOI ] |
| [90] |
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 ] |
| [91] |
G. Lagarde and S. Perifel. Lempel-Ziv: a “one-bit catastrophe” but not a tragedy. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1478--1495, 2018. [ DOI | arXiv ] |
| [92] |
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. [ www: | Abstract | PDF ] |
| [93] |
M. López-Valdés. Scaled dimension of individual strings. Technical Report TR06-047, Electronic Colloquium on Computational Complexity, 2006. [ Abstract ] |
| [94] |
M. López-Valdés and E. Mayordomo. Dimension is compression. Theory of Computing Systems, 52(1):95--112, 2013. [ DOI ] |
| [95] |
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 [97]. [ DOI ] |
| [96] |
J. H. Lutz. Dimension in complexity classes. SIAM Journal on Computing, 32(5):1236--1259, 2003. [ DOI | arXiv | PDF ] |
| [97] |
J. H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187(1):49--79, 2003. [ DOI | arXiv ] |
| [98] |
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 ] |
| [99] |
J. H. Lutz. Effective fractal dimensions. Mathematical Logic Quarterly, 51(1):62--72, 2005. [ DOI | PDF ] |
| [100] |
J. H. Lutz. A divergence formula for randomness and dimension. In Proceedings of the 5th Conference on Computability in Europe, 2009. [ DOI | arXiv | Abstract ] |
| [101] |
J. H. Lutz and N. Lutz. Algorithmic information, plane kakeya sets, and conditional dimension. ACM Trans. Comput. Theory, 10(2), 2018. [ DOI ] |
| [102] |
J. H. Lutz and N. Lutz. Who asked us? how the theory of computing answers questions about analysis. In D. Du and J. Wang, editors, Complexity and Approximation - In Memory of Ker-I Ko, volume 12000 of Lecture Notes in Computer Science, pages 48--56. Springer, 2020. [ DOI | arXiv ] |
| [103] |
J. H. Lutz, N. Lutz, and E. Mayordomo. The dimensions of hyperspaces. CoRR, abs/2004.07798, 2020. [ arXiv ] |
| [104] |
J. H. Lutz, N. Lutz, and E. Mayordomo. Dimension and the structure of complexity classes. Theory of Computing Systems, 67:473--490, 2023. [ DOI | arXiv ] |
| [105] |
J. H. Lutz, N. Lutz, and E. Mayordomo. Extending the reach of the point-to-set principle. Information and Computation, 294:105078, 2023. [ DOI | arXiv ] |
| [106] |
J. H. Lutz and E. Mayordomo. Dimensions of points in self-similar fractals. SIAM Journal on Computing, 38:1080--1112, 2008. [ PDF ] |
| [107] |
J. H. Lutz and E. Mayordomo. Algorithmic fractal dimensions in geometric measure theory. In V. Brattka and P. Hertling, editors, Handbook of Computability and Complexity in Analysis, pages 271--302. Springer International Publishing, 2021. [ DOI | arXiv ] |
| [108] |
J. H. Lutz and E. Mayordomo. Computing absolutely normal numbers in nearly linear time. Information and Computation, 281:104746, 2021. [ DOI | arXiv ] |
| [109] |
J. H. Lutz and A. N. Migunov. Algorithmic Dimensions via Learning Functions. In R. Královič and A. Kučera, editors, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1--72:13, Dagstuhl, Germany, 2024. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. [ DOI | arXiv | Abstract ] |
| [110] |
J. H. Lutz, S. Nandakumar, and S. Pulari. A Weyl criterion for finite-state dimension and applications. In J. Leroux, S. Lombardy, and D. Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs, pages 65:1--65:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. [ DOI | arXiv ] |
| [111] |
J. H. Lutz, R. Qi, and L. Yu. The point-to-set principle and the dimensions of Hamel bases. Computability, 13(2):105--112, 2024. [ DOI | arXiv ] |
| [112] |
J. H. Lutz and K. Weihrauch. Connectivity properties of dimension level sets. Mathematical Logic Quarterly, 54(5):483--491, 2008. [ DOI ] |
| [113] |
N. Lutz. A note on pointwise dimensions. CoRR, abs/1612.05849, 2016. [ arXiv ] |
| [114] |
N. Lutz. Fractal intersections and products via algorithmic dimension. ACM Transactions on Computation Theory, 13(3), 2021. [ DOI | arXiv ] |
| [115] |
N. Lutz and D. Stull. Dimension spectra of lines. Computability, 11:85--112, 2022. [ DOI ] |
| [116] |
N. Lutz and D. Stull. Projection theorems using effective dimension. Information and Computation, 297:105137, 2024. [ DOI ] |
| [117] |
N. Lutz and D. M. Stull. Bounding the dimension of points on a line. Information and Computation, 275:104601, 2020. [ DOI ] |
| [118] |
N. J. Lutz. Algorithmic Information, Fractal Geometry, and Distributed Dynamics. PhD thesis, Rutgers The State University of New Jersey, School of Graduate Studies, 2017. |
| [119] |
M. López-Valdés. Aplicaciones de la dimensión efectiva a la complejidad computacional y a los algoritmos de comprensión de datos. PhD thesis, Universidad de Zaragoza, 2011. [ Abstract ] |
| [120] |
A. Marcone and M. Valenti. Effective aspects of Hausdorff and Fourier dimension. Computability, 11:299--333, 2022. [ DOI ] |
| [121] |
E. Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Information Processing Letters, 84(1):1--3, 2002. [ DOI ] |
| [122] |
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. [ DOI | PostScript (gzipped) ] |
| [123] |
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 ] |
| [124] |
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 ] |
| [125] |
E. Mayordomo. Effective Hausdorff dimension in general metric spaces. Theory of Computing Systems, 62:1620--1636, 2018. [ DOI ] |
| [126] |
E. Mayordomo. A point to set principle for finite-state dimension. CoRR, abs/2208.00157, 2022. [ DOI | arXiv ] |
| [127] |
E. Mayordomo, P. Moser, and S. Perifel. Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable. Theory of Computing Systems, 48:731--766, 2011. [ DOI ] |
| [128] |
E. Mayordomo and A. Nies. Fractal dimensions and profinite groups. Technical report, arXiv, 2025. [ arXiv ] |
| [129] |
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 ] |
| [130] |
A. N. Migunov. Randomness and Dimension in Computational Learning and Analog Computation. PhD thesis, Iowa State University, 2022. [ Abstract ] |
| [131] |
J. S. Miller. Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension. Advances in Mathematics, 226(1):373--384, 2011. [ DOI ] |
| [132] |
J. S. Miller and A. Nies. Randomness and computability: open questions. Bulletin of Symbolic Logic, 12(3):390--410, 2006. [ DOI | PDF ] |
| [133] |
P. Moser. BPP has effective dimension at most 1/2 unless BPP = EXP. Technical Report TR03-029, Electronic Colloquium on Computational Complexity, 2003. [ Abstract | PDF ] |
| [134] |
P. Moser. Derandomization and Quantitative Complexity. PhD thesis, Université de Genève, 2004. |
| [135] |
P. Moser. Generic density and small span theorem. Information and Computation, 206(1):1--14, 2008. [ DOI ] |
| [136] |
P. Moser. Martingale families and dimension in P. Theoretical Computer Science, 400(1--3):46--61, 2008. [ DOI ] |
| [137] |
P. Moser. A zero-one SUBEXP-dimension law for BPP. Information Processing Letters, 111(9):429--432, 2011. [ DOI ] |
| [138] |
S. Nandakumar. A characterization of constructive dimension. Mathematical Logic Quarterly, 55(2):185--200, 2009. [ DOI ] |
| [139] |
S. Nandakumar. Dynamics, Measure, and Dimension in the Theory of Computing. PhD thesis, Iowa State University, 2009. [ Abstract ] |
| [140] |
S. Nandakumar and S. Pulari. Real numbers equally compressible in every base. In P. Berenbrink, P. Bouyer, A. Dawar, and M. M. Kanté, editors, 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany, volume 254 of LIPIcs, pages 48:1--48:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. [ DOI | arXiv ] |
| [141] |
S. Nandakumar, S. Pulari, and A. S. Finite-state relative dimension, dimensions of A. P. subsequences and a finite-state van Lambalgen's theorem. Inf. Comput., 298:105156, 2024. [ DOI ] |
| [142] |
S. Nandakumar, S. Pulari, and A. S. Point-to-set principle and constructive dimension faithfulness. In R. Královic and A. Kucera, editors, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia, volume 306 of LIPIcs, pages 76:1--76:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. [ DOI | arXiv ] |
| [143] |
S. Nandakumar, S. Pulari, A. S, and S. Sarma. One-way functions and polynomial time dimension. Technical report, arXiv, 2025. [ DOI | arXiv ] |
| [144] |
S. Nandakumar, A. S, and P. Vishnoi. Effective continued fraction dimension versus effective Hausdorff dimension of reals. In J. Leroux, S. Lombardy, and D. Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs, pages 70:1--70:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. [ DOI | arXiv ] |
| [145] |
S. Nandakumar and S. K. Vangapelli. Normality and finite-state dimension of liouville numbers. Theory Comput. Syst., 58(3):392--402, 2016. [ DOI ] |
| [146] |
S. Nandakumar and P. Vishnoi. Randomness and Effective Dimension of Continued Fractions. In J. Esparza and D. Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 73:1--73:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. [ DOI | Abstract ] |
| [147] |
K. M. Ng. Computability, Traceability and Beyond. PhD thesis, Victoria University of Wellington, 2009. [ PDF ] |
| [148] |
J. Nichols. Pushdown gamblers and pushdown dimension. Master's thesis, Iowa State University, Ames, IA, USA, 2004. [ DOI | Abstract ] |
| [149] |
A. Nies. Computability and randomness, volume 51 of Oxford Logic Guides. Oxford University Press, 2009. |
| [150] |
A. Nies and J. Reimann. A lower cone in the wtt degrees of non-integral effective dimension. In Computational Prospects of Infinity, pages 249--260, 2008. [ DOI | PDF ] |
| [151] |
T. Orponen. Combinatorial proofs of two theorems of Lutz and Stull. Mathematical Proceedings of the Cambridge Philosophical Society, 171(3):503--514, 2021. [ DOI ] |
| [152] |
C. P. Porter. Length functions and the dimension of points in self-similar fractal trees. IEEE Transactions on Information Theory, 69(10):6221--6230, 2023. [ DOI ] |
| [153] |
S. Reid. The classes of algorithmically random reals. Master's thesis, Victoria University of Wellington, 2003. [ Abstract ] |
| [154] |
J. Reimann. Computability and fractal dimension. PhD thesis, Ruprecht-Karls Universität Heidelberg, 2004. [ DOI ] |
| [155] |
J. Reimann. Effectively closed sets of measures and randomness. Annals of Pure and Applied Logic, 156:170--182, 2008. [ DOI | DOI | PDF ] |
| [156] |
J. Reimann. Randomness beyond Lebesgue measure. In Proceedings of Logic Colloquium 2006, 2009. |
| [157] |
J. Reimann. Information vs. Dimension: An algorithmic perspective, pages 111--151. World Scientific Publishing Co., United States, Jan. 2020. [ DOI ] |
| [158] |
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. |
| [159] |
J. Reimann and F. Stephan. Hierarchies of randomness tests. In Proceedings of the 9th Asian Logic Conference. World Scientific Publishing, 2006. [ PDF ] |
| [160] |
L. Richter. Co-analytic counterexamples to marstrand's projection theorem. Technical report, arXiv, 2023. [ arXiv ] |
| [161] |
L. Richter. On the Definability and Complexity of Sets and Structures. PhD thesis, Victoria University of Wellington, 2024. [ DOI | Abstract ] |
| [162] |
T. Slaman. On capacitability for co-analytic sets. New Zealand Journal of Mathematics, 52:865--869, 2021. [ DOI ] |
| [163] |
L. Staiger. Constructive dimension equals Kolmogorov complexity. Information Processing Letters, 93(3):149--153, 2005. [ DOI | PDF ] |
| [164] |
L. Staiger. Exact constructive and computable dimensions. Theory of Computing Systems, 61(4):1288--1314, 2017. [ DOI ] |
| [165] |
F. Stephan. Hausdorff-dimension and weak truth-table reducibility. In D. Z. K. Kearnes, A. Andretta, editor, Logic Colloquium 2004, volume 29 of Lecture Notes in Logic, pages 157--167. Association for Symbolic Logic, 2008. |
| [166] |
D. M. Stull. Algorithmic Randomness and Analysis. PhD thesis, Iowa State University, 2017. [ Abstract ] |
| [167] |
D. M. Stull. Resource bounded randomness and its applications. In J. N. Y. Franklin and C. P. Porter, editors, Algorithmic Randomness: Progress and Prospects, volume 50 of Lecture Notes in Logic, page 301–348. Cambridge University Press, Cambridge, 2020. [ DOI ] |
| [168] |
D. M. Stull. The dimension spectrum conjecture for planar lines. In M. Bojanczyk, E. Merelli, and D. P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 133:1--133:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. [ DOI ] |
| [169] |
D. M. Stull. Optimal oracles for point-to-set principles. In P. Berenbrink and B. Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference), volume 219 of LIPIcs, pages 57:1--57:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. [ DOI | arXiv ] |
| [170] |
D. M. Stull. Pinned distance sets using effective dimension. CoRR, abs/2207.12501, 2022. [ DOI | arXiv ] |
| [171] |
C. Sureson. Subcomputable Hausdorff function dimension. Theor. Comput. Sci., 891:59--83, 2021. [ DOI ] |
| [172] |
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 | DOI ] |
| [173] |
S. A. Terwijn. Complexity and randomness. Rendiconti del Seminario Matematico di Torino, 62(1):1--38, 2004. [ PDF ] |
| [174] |
D. Turetsky. Connectedness properties of dimension level sets. Manuscript, 2009. [ PDF ] |
| [175] |
P. W. Tveite. Effectivizations of Dimension and Cardinal Characteristics. PhD thesis, University of Wisconsin-Madison, 2017. [ Abstract ] |
| [176] |
F. Wang. Kolmogorov extraction and resource-bounded zero-one laws. Master's thesis, Iowa State University, 2006. [ Abstract ] |
| [177] |
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. [ arXiv | Abstract | PDF ] |
This file was generated by bibtex2html 1.99.
UWYO Essay service topgradeessay.com