| [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. Costa, A. Matos, and P. Vitányi. Computational depth of infinite strings revisited. In Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007: local proceedings, pages 36--44. 2007. [ Abstract | PDF ] |
| [7] |
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 ] |
| [8] |
V. Arvind. Normal numbers and algorithmic randomness: a historical sketch. Current Science, 106(12):1687--1692, 2014. [ Abstract ] |
| [9] |
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 ] |
| [10] |
M. Bachan. Finite-state dimension of the Kolakoski sequence. Master's thesis, Iowa State University, Ames, IA, USA, 2005. [ Abstract ] |
| [11] |
G. Barmpalias and L. Liu. Aspects of Muchnik's paradox in restricted betting. Technical Report 2201.07007, arXiv, 2022. [ arXiv ] |
| [12] |
G. Barmpalias and A. Shen. The Kučera--Gács theorem revisited by Levín. Theoretical Computer Science, 947:113693, 2023. [ DOI ] |
| [13] |
V. Becher, O. Carton, and S. Figueira. Rauzy dimension and finite-state dimension. Technical report, arXiv, 2024. [ DOI | arXiv ] |
| [14] |
V. Becher and P. A. Heiber. Normal numbers and finite automata. Theoretical Computer Science, 477:109--116, 2013. [ DOI | Abstract ] |
| [15] |
V. Becher, J. Reimann, and T. A. Slaman. Irrationality exponent, Hausdorff dimension and effectivization. Monatshefte für Mathematik, 185:167--188, 2018. [ DOI ] |
| [16] |
R. Beigel, L. Fortnow, and F. Stephan. Infinitely-often autoreducible sets. SIAM Journal on Computing, 36(3):595--608, 2006. [ DOI ] |
| [17] |
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 ] |
| [18] |
L. Bienvenu. Caractérisations de l'aléatoire par les jeux: imprédictibilité et stochasticité. PhD thesis, Université de Provence, 2008. [ PDF ] |
| [19] |
L. Bienvenu, D. Doty, and F. Stephan. Constructive dimension and Turing degrees. Theory of Computing Systems, 45(4):740--755, 2009. [ DOI | arXiv ] |
| [20] |
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 ] |
| [21] |
C. Bourke. Finite-state dimension of individual sequences. Master's thesis, University of Nebraska-Lincoln, 2004. [ PDF ] |
| [22] |
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 ] |
| [23] |
C. S. Calude, K. Salomaa, and T. K. Roblot. Finite state complexity. Theoretical Computer Science, 412(41):5668--5677, 2011. [ DOI | Abstract ] |
| [24] |
C. S. Calude, L. Staiger, and F. Stephan. Finite state incompressible infinite sequences. Information and Computation, 247:23--36, 2016. [ DOI ] |
| [25] |
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 ] |
| [26] |
C. S. Calude and M. Zimand. Algorithmically independent sequences. Information and Computation, 208(3):292--308, 2010. [ DOI | arXiv ] |
| [27] |
W. Calvert, E. Gruner, E. Mayordomo, D. Turetsky, and J. D. Villano. Normality, relativization, and randomness. Preprint 2312.10204v2, arXiv, February 2025. [ arXiv ] |
| [28] |
A. Case. Bounded Turing reductions and data processing inequalities for sequences. Theory of Computing Systems, 62(7):1586--1598, 2018. [ DOI | arXiv ] |
| [29] |
A. Case and J. H. Lutz. Mutual dimension. ACM Transactions on Computation Theory (TOCT), 7(3):1--26, 2015. [ DOI | arXiv ] |
| [30] |
A. Case and J. H. Lutz. Mutual dimension and random sequences. Theoretical Computer Science, 731:68--87, 2018. [ DOI | arXiv ] |
| [31] |
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 | arXiv ] |
| [32] |
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 ] |
| [33] |
A. T. Case. Mutual dimension, data processing inequalities, and randomness. Phd thesis, Iowa State University, 2016. [ Abstract ] |
| [34] |
C. J. Conidis. Effective Packing Dimension Of Π01-Classes. Proceedings of the American Mathematical Society, 136(10):3655--3662, 2008. [ DOI ] |
| [35] |
C. J. Conidis. Applications of computability theory. PhD thesis, University of Chicago, 2009. [ Abstract ] |
| [36] |
C. J. Conidis. A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one. The Journal of Symbolic Logic, 77(2):447--474, 2012. [ DOI ] |
| [37] |
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 ] |
| [38] |
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 ] |
| [39] |
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 ] |
| [40] |
D. Doty. Dimension extractors and optimal decompression. Theory of Computing Systems, 43(3--4):425--463, 2008. [ DOI | arXiv ] |
| [41] |
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 ] |
| [42] |
D. Doty, J. H. Lutz, and S. Nandakumar. Finite-state dimension and real arithmetic. Information and Computation, 205(11):1640--1651, 2007. [ DOI | arXiv | PDF ] |
| [43] |
D. Doty and P. Moser. Finite-state dimension and lossy decompressors. Technical Report arXiv:cs/0609096 [cs.CC], arXiv, 2006. [ arXiv ] |
| [44] |
D. Doty and P. Moser. Feasible depth. In Proceedings of the 3rd Conference on Computability in Europe, pages 228--237. Springer-Verlag, 2007. [ DOI | arXiv ] |
| [45] |
D. Doty and J. Nichols. Pushdown dimension. Theoretical Computer Science, 381(1--3):105--123, 2007. [ DOI | arXiv ] |
| [46] |
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 | PDF ] |
| [47] |
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 ] |
| [48] |
R. Downey. Algorithmic randomness and computability. Manuscript, 2009. [ PDF ] |
| [49] |
R. Downey. Randomness, computation and mathematics. In S. B. Cooper, A. Dawar, and B. Löwe, editors, How the World Computes, pages 162--181, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. [ DOI ] |
| [50] |
R. Downey. Computability theory, algorithmic randomness and Turing's anticipation. In R. Downey, editor, Turing's Legacy: Developments from Turing's Ideas in Logic, Lecture Notes in Logic, pages 90--123. Cambridge University Press, 2014. [ DOI ] |
| [51] |
R. Downey. Turing and randomness. In J. Copeland, J. P. Bowen, M. D. Sprevak, and R. Wilson, editors, The Turing Guide, pages 427--435. Oxford University Press, 2017. [ DOI | PDF ] |
| [52] |
R. Downey and N. Greenberg. Turing degrees of reals of positive effective packing dimension. Information Processing Letters, 108(5):298--303, 2008. [ DOI ] |
| [53] |
R. Downey and D. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 2010. [ DOI ] |
| [54] |
R. Downey and D. R. Hirschfeldt. Algorithmic randomness. Communications of the ACM, 62(5):70--80, 4 2019. [ DOI ] |
| [55] |
R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn. Calibrating randomness. Bulletin of Symbolic Logic, 12(3):411--491, 2006. [ DOI ] |
| [56] |
R. Downey, W. Merkle, and J. Reimann. Schnorr dimension. Mathematical Structures in Computer Science, 16(5):789--811, 2006. [ DOI | PDF ] |
| [57] |
R. Downey and K. M. Ng. Effective Packing Dimension and Traceability. Notre Dame Journal of Formal Logic, 51(2):279 -- 290, 2010. [ DOI | DOI ] |
| [58] |
R. Downey and J. Stephenson. Avoiding effective packing dimension 1 below array noncomputable c.e. degrees. The Journal of Symbolic Logic, 83(2):717--739, 2018. [ DOI ] |
| [59] |
A. Drucker. High-confidence predictions under adversarial uncertainty. ACM Transactions on Computation Theory, 5(3):12:1--12:18, 2013. [ DOI | arXiv ] |
| [60] |
S. A. Fenner. Gales and supergales are equivalent for defining constructive Hausdorff dimension. Technical Report arXiv:cs/0208044 [cs.CC], arXiv, 2002. [ arXiv | Abstract | PDF ] |
| [61] |
J. B. Fiedler and D. M. Stull. Dimension of pinned distance sets for semi-regular sets. Technical Report 2309.11701, arXiv, 2023. [ arXiv ] |
| [62] |
J. B. Fiedler and D. M. Stull. Pinned distances of planar sets with low dimension. Technical Report 2408.00889, arXiv, 2025. [ arXiv ] |
| [63] |
J. B. Fiedler and D. M. Stull. Universal sets for projections. Technical Report 2411.16001, arXiv, 2025. [ arXiv ] |
| [64] |
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 ] |
| [65] |
L. Fortnow and J. H. Lutz. Prediction and dimension. Journal of Computer and System Sciences, 70(4):570--589, 2005. [ DOI | PDF ] |
| [66] |
C. Fraize. Aspects of Algorithmically Random Objects. PhD thesis, University of Florida, 2023. [ Abstract ] |
| [67] |
C. Fraize and C. P. Porter. Kolmogorov complexity and generalized length functions. Technical Report 1611.05819, arXiv, 2016. [ arXiv ] |
| [68] |
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 ] |
| [69] |
R. Gavaldà, M. López-Valdés, E. Mayordomo, and N. V. Vinodchandran. Resource-bounded dimension in computational learning theory. Technical Report 1010.5470, arXiv, 2010. [ arXiv ] |
| [70] |
N. Greenberg and J. S. Miller. Diagonally non-recursive functions and effective Hausdorff dimension. Bulletin of the London Mathematical Society, 43(4):636--654, 2011. [ DOI ] |
| [71] |
N. Greenberg, J. S. Miller, A. Shen, and L. B. Westrick. Dimension 1 sequences are close to randoms. Theoretical Computer Science, 705:99--112, 2018. [ DOI | arXiv ] |
| [72] |
X. Gu. A note on dimensions of polynomial size circuits. Theoretical Computer Science, 359(1--3):176--187, 2006. [ DOI ] |
| [73] |
X. Gu. Fractals in complexity and geometry. PhD thesis, Iowa State University, 2009. [ Abstract ] |
| [74] |
X. Gu and J. H. Lutz. Dimension characterizations of complexity classes. Computational Complexity, 17:459--474, 2008. [ DOI | PDF ] |
| [75] |
X. Gu and J. H. Lutz. Effective dimensions and relative frequencies. Theor. Comput. Sci., 412(48):6696--6711, 2011. [ DOI | arXiv | PDF ] |
| [76] |
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 ] |
| [77] |
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 | PDF ] |
| [78] |
X. Gu, J. H. Lutz, and P. Moser. Dimensions of Copeland-Erdös sequences. Information and Computation, 205(9):1317--1333, 2007. [ DOI | PDF ] |
| [79] |
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 ] |
| [80] |
M. Hauptmann. Scaled dimension and the Berman-Hartmanis conjecture. Technical Report 85300-CS, University of Bonn, 2008. [ Abstract | PDF ] |
| [81] |
P. A. Heiber. Una perspectiva computacional sobre números normales. PhD thesis, University of Buenos Aires, 2014. [ PDF ] |
| [82] |
I. Herbert. A perfect set of reals with finite self-information. The Journal of Symbolic Logic, 78(4):1229--1246, 2013. [ DOI | arXiv ] |
| [83] |
D. R. Hirschfeldt and S. A. Terwijn. Limit Computability and Constructive Measure, pages 131--141. World Scientific, 2008. [ DOI ] |
| [84] |
D. R. Hirschfeldt and R. Weber. Finite self-information. Computability, 1(1):85--98, 2012. [ DOI ] |
| [85] |
J. M. Hitchcock. Resource-bounded dimension, nonuniform complexity, and approximation of MAX3SAT. Master's thesis, Iowa State University, Ames, IA, USA, 2001. [ DOI | Abstract ] |
| [86] |
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 ] |
| [87] |
J. M. Hitchcock. Effective Fractal Dimension: Foundations and Applications. PhD thesis, Iowa State University, 2003. [ Abstract | PostScript | PDF ] |
| [88] |
J. M. Hitchcock. Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science, 304(1--3):431--441, 2003. [ DOI | Abstract | PDF ] |
| [89] |
J. M. Hitchcock. Gales suffice for constructive dimension. Information Processing Letters, 86(1):9--12, 2003. [ DOI | arXiv | Abstract | PDF ] |
| [90] |
J. M. Hitchcock. Small spans in scaled dimension. SIAM Journal on Computing, 34(1):170--194, 2004. [ DOI | arXiv | Abstract | PDF ] |
| [91] |
J. M. Hitchcock. Correspondence principles for effective dimensions. Theory of Computing Systems, 38(5):559--571, 2005. [ DOI | Abstract | PDF ] |
| [92] |
J. M. Hitchcock. Hausdorff dimension and oracle constructions. Theoretical Computer Science, 355(3):382--388, 2006. [ DOI | Abstract | PDF ] |
| [93] |
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 ] |
| [94] |
J. M. Hitchcock. Limitations of efficient reducibility to the Kolmogorov random strings. Computability, 1(1):39--43, 2012. [ DOI | Abstract | PDF ] |
| [95] |
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 ] |
| [96] |
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 ] |
| [97] |
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 ] |
| [98] |
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 ] |
| [99] |
J. M. Hitchcock and E. Mayordomo. Base invariance of feasible dimension. Information Processing Letters, 113(14-16):546--551, 2013. [ DOI | Abstract | PDF ] |
| [100] |
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 ] |
| [101] |
J. M. Hitchcock and A. Pavan. Hardness hypotheses, derandomization, and circuit complexity. Computational Complexity, 17(1):119--146, 2008. [ DOI | Abstract | PDF ] |
| [102] |
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 ] |
| [103] |
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 ] |
| [104] |
M. Hoyrup. The dimension of ergodic random sequences. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of Leibniz International Proceedings in Informatics (LIPIcs), pages 567--576, 2012. [ DOI | arXiv ] |
| [105] |
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 ] |
| [106] |
H. Imai, M. Kumabe, K. Miyabe, Y. Mizusawa, and T. Suzuki. Rational sequences converging to left-c.e. reals of positive effective Hausdorff dimension. In Computability Theory and Foundations of Mathematics, pages 97--121. [ DOI ] |
| [107] |
J. J. Joosten, F. Soler-Toscano, and H. Zenil. Fractal dimension versus process complexity. Advances in Mathematical Physics, 2016(1):5030593, 2016. [ DOI ] |
| [108] |
L. Jordon. An Investigation of Feasible Logical Depth and Complexity Measures Via Automata and Compression Algorithms. PhD thesis, Maynooth University, 2022. [ Abstract ] |
| [109] |
L. Jordon, P. Maguire, and P. Moser. Pebble-depth. Theoretical Computer Science, 1009:114638, 2024. [ DOI ] |
| [110] |
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 ] |
| [111] |
B. Kastermans and S. Lempp. Comparing notions of randomness. Theoretical Computer Science, 411(3):602--616, 2010. [ DOI ] |
| [112] |
B. Kjos-Hanssen. Infinite subsets of random sets of integers. Technical Report 1408.2881, arXiv, 2014. [ arXiv ] |
| [113] |
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 ] |
| [114] |
B. Kjos-Hanssen and D. J. Webb. KL-randomness and effective dimension under strong reducibility. In L. D. Mol, A. Weiermann, F. Manea, and D. Fernández-Duque, editors, Connecting with Computability - 17th Conference on Computability in Europe, CiE 2021, Virtual Event, Ghent, July 5-9, 2021, Proceedings, volume 12813 of Lecture Notes in Computer Science, pages 457--468. Springer, 2021. [ DOI | arXiv ] |
| [115] |
A. Kozachinskiy and A. Shen. Two characterizations of finite-state dimension. In Fundamentals of Computation Theory, pages 80--94. Springer International Publishing, 2019. [ DOI ] |
| [116] |
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 ] |
| [117] |
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 ] |
| [118] |
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 ] |
| [119] |
S. Lempp, J. S. Miller, K. M. Ng, D. D. Turetsky, and R. Weber. Lowness for effective Hausdorff dimension. Journal of Mathematical Logic, 14(02):1450011, 2014. [ DOI ] |
| [120] |
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 ] |
| [121] |
M. López-Valdés. Scaled dimension of individual strings. Technical Report TR06-047, Electronic Colloquium on Computational Complexity, 2006. [ Abstract ] |
| [122] |
M. López-Valdés and E. Mayordomo. Dimension is compression. Theory of Computing Systems, 52(1):95--112, 2013. [ DOI ] |
| [123] |
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 [125]. [ DOI ] |
| [124] |
J. H. Lutz. Dimension in complexity classes. SIAM Journal on Computing, 32(5):1236--1259, 2003. [ DOI | arXiv | PDF ] |
| [125] |
J. H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187(1):49--79, 2003. [ DOI | arXiv | PDF ] |
| [126] |
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 ] |
| [127] |
J. H. Lutz. Effective fractal dimensions. Mathematical Logic Quarterly, 51(1):62--72, 2005. [ DOI | PDF ] |
| [128] |
J. H. Lutz. A divergence formula for randomness and dimension. Theoretical Computer Science, 412(1):166--177, 2011. [ DOI | arXiv | PDF ] |
| [129] |
J. H. Lutz and N. Lutz. Algorithmic information, plane kakeya sets, and conditional dimension. ACM Trans. Comput. Theory, 10(2), 2018. [ DOI | arXiv ] |
| [130] |
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 ] |
| [131] |
J. H. Lutz, N. Lutz, and E. Mayordomo. The dimensions of hyperspaces. CoRR, abs/2004.07798v1, 2020. Revised as [133]. [ arXiv ] |
| [132] |
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 ] |
| [133] |
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 ] |
| [134] |
J. H. Lutz and E. Mayordomo. Dimensions of points in self-similar fractals. SIAM Journal on Computing, 38:1080--1112, 2008. [ PDF ] |
| [135] |
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 ] |
| [136] |
J. H. Lutz and E. Mayordomo. Computing absolutely normal numbers in nearly linear time. Information and Computation, 281:104746, 2021. [ DOI | arXiv ] |
| [137] |
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 ] |
| [138] |
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 ] |
| [139] |
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 ] |
| [140] |
J. H. Lutz and K. Weihrauch. Connectivity properties of dimension level sets. Mathematical Logic Quarterly, 54(5):483--491, 2008. [ DOI | PDF ] |
| [141] |
N. Lutz. A note on pointwise dimensions. CoRR, abs/1612.05849, 2016. [ arXiv ] |
| [142] |
N. Lutz. Some open problems in algorithmic fractal geometry. ACM SIGACT News, 48(4):35--41, 2017. [ DOI | PDF ] |
| [143] |
N. Lutz. Fractal intersections and products via algorithmic dimension. ACM Transactions on Computation Theory, 13(3), 2021. [ DOI | arXiv ] |
| [144] |
N. Lutz and D. Stull. Dimension spectra of lines. Computability, 11:85--112, 2022. [ DOI | arXiv ] |
| [145] |
N. Lutz and D. Stull. Projection theorems using effective dimension. Information and Computation, 297:105137, 2024. [ DOI | arXiv ] |
| [146] |
N. Lutz and D. M. Stull. Bounding the dimension of points on a line. Information and Computation, 275:104601, 2020. [ DOI | arXiv ] |
| [147] |
N. J. Lutz. Algorithmic Information, Fractal Geometry, and Distributed Dynamics. PhD thesis, Rutgers The State University of New Jersey, 2017. [ Abstract ] |
| [148] |
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 ] |
| [149] |
A. Marcone and M. Valenti. Effective aspects of Hausdorff and Fourier dimension. Computability, 11:299--333, 2022. [ DOI ] |
| [150] |
E. Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Information Processing Letters, 84(1):1--3, 2002. [ DOI ] |
| [151] |
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) ] |
| [152] |
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 ] |
| [153] |
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 ] |
| [154] |
E. Mayordomo. Effective Hausdorff dimension in general metric spaces. Theory of Computing Systems, 62:1620--1636, 2018. [ DOI ] |
| [155] |
E. Mayordomo. A point to set principle for finite-state dimension. CoRR, abs/2208.00157, 2022. [ DOI | arXiv ] |
| [156] |
E. Mayordomo. Una generalización del teorema de proyección de Marstrand. La Gaceta de la RSME, 25(2):343--352, 2022. [ PDF ] |
| [157] |
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 ] |
| [158] |
E. Mayordomo and A. Nies. Fractal dimensions and profinite groups. Technical Report 2502.09995, arXiv, 2025. [ arXiv ] |
| [159] |
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 ] |
| [160] |
A. N. Migunov. Randomness and Dimension in Computational Learning and Analog Computation. PhD thesis, Iowa State University, 2022. [ Abstract ] |
| [161] |
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 ] |
| [162] |
J. S. Miller and A. Nies. Randomness and computability: open questions. Bulletin of Symbolic Logic, 12(3):390--410, 2006. [ DOI | PDF ] |
| [163] |
K. Miyabe, A. Nies, and F. Stephan. Randomness and Solovay degrees. Journal of Logic & Analysis, 10(3):1--13, 2018. [ DOI ] |
| [164] |
P. Moser. BPP has effective dimension at most 1/2 unless BPP = EXP. Technical Report TR03-029, Electronic Colloquium on Computational Complexity, 2003. [ Abstract ] |
| [165] |
P. Moser. Derandomization and Quantitative Complexity. PhD thesis, Université de Genève, 2004. |
| [166] |
P. Moser. Generic density and small span theorem. Information and Computation, 206(1):1--14, 2008. [ DOI ] |
| [167] |
P. Moser. Martingale families and dimension in P. Theoretical Computer Science, 400(1--3):46--61, 2008. [ DOI ] |
| [168] |
P. Moser. A zero-one SUBEXP-dimension law for BPP. Information Processing Letters, 111(9):429--432, 2011. [ DOI ] |
| [169] |
S. Nandakumar. A characterization of constructive dimension. Mathematical Logic Quarterly, 55(2):185--200, 2009. [ DOI ] |
| [170] |
S. Nandakumar. Dynamics, Measure, and Dimension in the Theory of Computing. PhD thesis, Iowa State University, 2009. [ Abstract ] |
| [171] |
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 ] |
| [172] |
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 ] |
| [173] |
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 ] |
| [174] |
S. Nandakumar, S. Pulari, A. S, and S. Sarma. One-way functions and polynomial time dimension. Technical Report 2411.02392, arXiv, 2025. [ DOI | arXiv ] |
| [175] |
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 ] |
| [176] |
S. Nandakumar and S. K. Vangapelli. Normality and finite-state dimension of Liouville numbers. Theory Comput. Syst., 58(3):392--402, 2016. [ DOI ] |
| [177] |
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 ] |
| [178] |
K. M. Ng. Computability, Traceability and Beyond. PhD thesis, Victoria University of Wellington, 2009. [ Abstract ] |
| [179] |
J. Nichols. Pushdown gamblers and pushdown dimension. Master's thesis, Iowa State University, Ames, IA, USA, 2004. [ DOI | Abstract ] |
| [180] |
A. Nies. Computability and randomness, volume 51 of Oxford Logic Guides. Oxford University Press, 2009. |
| [181] |
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 ] |
| [182] |
K. Okamura. Random sequences with respect to a measure defined by two linear fractional transformations. Theory of Computing Systems, 57(1):226--237, 2015. [ DOI ] |
| [183] |
T. Orponen. Combinatorial proofs of two theorems of Lutz and Stull. Mathematical Proceedings of the Cambridge Philosophical Society, 171(3):503--514, 2021. [ DOI ] |
| [184] |
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 ] |
| [185] |
J. Ratsaby. Fractal information density. Chaos, Solitons & Fractals, 192:115989, 2025. [ DOI ] |
| [186] |
S. Reid. The classes of algorithmically random reals. Master's thesis, Victoria University of Wellington, 2003. [ Abstract ] |
| [187] |
J. Reimann. Computability and fractal dimension. PhD thesis, Ruprecht-Karls Universität Heidelberg, 2004. [ DOI ] |
| [188] |
J. Reimann. Effectively closed sets of measures and randomness. Annals of Pure and Applied Logic, 156:170--182, 2008. [ DOI ] |
| [189] |
J. Reimann. Randomness beyond Lebesgue measure. In Proceedings of Logic Colloquium 2006, 2009. |
| [190] |
J. Reimann. Information vs. dimension: An algorithmic perspective. In Structure And Randomness In Computability And Set Theory, pages 111--151. World Scientific Publishing, 2020. [ DOI | arXiv ] |
| [191] |
J. Reimann and F. Stephan. Effective Hausdorff dimension. In M. Baaz, S.-D. Friedman, and J. Krajíček, editors, Logic Colloquium '01, volume 20 of Lecture Notes in Logic, pages 369--385. Cambridge University Press, 2005. [ DOI ] |
| [192] |
J. Reimann and F. Stephan. Hierarchies of randomness tests. In Mathematical Logic in Asia, pages 215--232. World Scientific Publishing, 2006. [ DOI ] |
| [193] |
L. Richter. Co-analytic counterexamples to marstrand's projection theorem. Technical Report 2301.06684, arXiv, 2023. [ arXiv ] |
| [194] |
L. Richter. On the Definability and Complexity of Sets and Structures. PhD thesis, Victoria University of Wellington, 2024. [ DOI | Abstract ] |
| [195] |
S. G. Simpson. Mass problems associated with effectively closed sets. Tohoku Mathematical Journal, Second Series, 63(4):489--517, 2011. [ DOI ] |
| [196] |
T. Slaman. On capacitability for co-analytic sets. New Zealand Journal of Mathematics, 52:865--869, 2021. [ DOI ] |
| [197] |
S. Song and L. Yu. On the Hausdorff dimension of maximal chains and antichains of Turing and hyperarithmetic degrees. Technical Report 2504.04957, arXiv, 2025. [ arXiv ] |
| [198] |
L. Staiger. Constructive dimension equals Kolmogorov complexity. Information Processing Letters, 93(3):149--153, 2005. [ DOI | PDF ] |
| [199] |
L. Staiger. A correspondence principle for exact constructive dimension. In S. B. Cooper, A. Dawar, and B. Löwe, editors, How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings, volume 7318 of Lecture Notes in Computer Science, pages 686--695. Springer, 2012. [ DOI | DOI ] |
| [200] |
L. Staiger. Exact constructive and computable dimensions. Theory of Computing Systems, 61(4):1288--1314, 2017. [ DOI ] |
| [201] |
L. Staiger. Finite automata and randomness. In S. Konstantinidis and G. Pighizzini, editors, Descriptional Complexity of Formal Systems, pages 1--10. Springer International Publishing, 2018. [ DOI ] |
| [202] |
L. Staiger. On the incomputability of computable dimension. Logical Methods in Computer Science, 16(2), May 2020. [ DOI | arXiv ] |
| [203] |
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. [ DOI ] |
| [204] |
J. Stephenson. Topics in computability theory: Boolean algebras and effective packing dimension. PhD thesis, 2014. [ Abstract ] |
| [205] |
J. Stephenson. Controlling effective packing dimension of Δ02 degrees. Notre Dame Journal of Formal Logic, 57(1):73--93, 2016. [ DOI | DOI ] |
| [206] |
D. M. Stull. Algorithmic Randomness and Analysis. PhD thesis, Iowa State University, 2017. [ Abstract ] |
| [207] |
D. M. Stull. Results on the Dimension Spectra of Planar Lines. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), pages 79:1--79:15, 2018. [ DOI ] |
| [208] |
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 ] |
| [209] |
D. M. Stull. The dimension spectrum conjecture for planar lines. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, pages 133:1--133:20, 2022. [ DOI | arXiv ] |
| [210] |
D. M. Stull. Optimal oracles for point-to-set principles. In Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, pages 57:1--57:17, 2022. [ DOI | arXiv ] |
| [211] |
D. M. Stull. Pinned distance sets using effective dimension. Technical Report 2207.12501, arXiv, 2022. [ DOI | arXiv ] |
| [212] |
C. Sureson. Subcomputable Hausdorff function dimension. Theoretical Computer Science, 891:59--83, 2021. [ DOI ] |
| [213] |
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 ] |
| [214] |
S. A. Terwijn. Complexity and randomness. Rendiconti del Seminario Matematico di Torino, 62(1):1--38, 2004. [ PDF ] |
| [215] |
F. Toska. Effective Symbolic Dynamics and Complexity. PhD thesis, University of Florida, 2013. [ Abstract ] |
| [216] |
D. Turetsky. Connectedness properties of dimension level sets. Manuscript, 2009. [ PDF ] |
| [217] |
P. W. Tveite. Effectivizations of Dimension and Cardinal Characteristics. PhD thesis, University of Wisconsin-Madison, 2017. [ Abstract ] |
| [218] |
A. van der Hulst. Kolmogorov complexity as a tool for computing Hausdorff dimension. Master's thesis, Radboud University Nijmegen, 2025. [ PDF ] |
| [219] |
V. Vassilevska, R. Williams, and S. L. M. Woo. Confronting hardness using a hybrid approach. Technical Report CMU-CS-05-125, School of Computer Science, Carnegie Mellon University, April 2005. [ Abstract | PDF ] |
| [220] |
F. Wang. Kolmogorov extraction and resource-bounded zero-one laws. Master's thesis, Iowa State University, 2006. [ Abstract ] |
| [221] |
R. D. Wasson. Data compression and fractal dimension for measures. Master's thesis, The Pennsylvania State University, December 2015. [ Abstract ] |
| [222] |
D. J. Webb. On New Notions of Algorithmic Dimension, Immunity, and Medvedev Degree. PhD thesis, University of Hawaii at Manoa, 2022. [ Abstract ] |
| [223] |
R. Williams. Defying hardness with a hybrid approach. Technical Report CMU-CS-04-159, School of Computer Science, Carnegie Mellon University, August 2004. [ Abstract | PDF ] |
| [224] |
M. Zimand. Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. Theory of Computing Systems, 46(4):707--722, 2010. [ DOI | arXiv ] |
| [225] |
M. Zimand. Possibilities and impossibilities in Kolmogorov complexity extraction. Technical Report 1104.0872, arXiv, 2011. [ arXiv ] |
This file was generated by bibtex2html 1.99.
UWYO Essay service topgradeessay.com