{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T17:22:12Z","timestamp":1764350532823},"publisher-location":"Cham","reference-count":48,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030416713"},{"type":"electronic","value":"9783030416720"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-41672-0_4","type":"book-chapter","created":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T02:03:04Z","timestamp":1582164184000},"page":"48-56","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Who Asked Us? How the Theory of Computing Answers Questions about Analysis"],"prefix":"10.1007","author":[{"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[]},{"given":"Neil","family":"Lutz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"issue":"3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1137\/S0097539703446912","volume":"37","author":"KB Athreya","year":"2007","unstructured":"Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension in algorithmic information and computational complexity. SIAM J. Comput. 37(3), 671\u2013705 (2007)","journal-title":"SIAM J. Comput."},{"key":"4_CR2","first-page":"105","volume":"2","author":"AS Besicovitch","year":"1919","unstructured":"Besicovitch, A.S.: Sur deux questions d\u2019int\u00e9grabilit\u00e9 des fonctions. J. de la Soci?t? de physique et de mathematique de l\u2019Universite de Perm 2, 105\u2013123 (1919)","journal-title":"J. de la Soci?t? de physique et de mathematique de l\u2019Universite de Perm"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01171101","volume":"27","author":"AS Besicovitch","year":"1928","unstructured":"Besicovitch, A.S.: On Kakeya\u2019s problem and a similar one. Math. Z. 27, 312\u2013320 (1928)","journal-title":"Math. Z."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"4433","DOI":"10.1090\/S0002-9947-96-01750-3","volume":"348","author":"CJ Bishop","year":"1996","unstructured":"Bishop, C.J., Peres, Y.: Packing dimension and Cartesian products. Trans. Am. Math. Soc. 348, 4433\u20134445 (1996)","journal-title":"Trans. Am. Math. Soc."},{"issue":"5","key":"4_CR5","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1137\/S009753979325456X","volume":"24","author":"AW Chou","year":"1995","unstructured":"Chou, A.W., Ko, K.: Computational complexity of two-dimensional regions. SIAM J. Comput. 24(5), 923\u2013947 (1995)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"4_CR6","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1002\/malq.200310120","volume":"50","author":"AW Chou","year":"2004","unstructured":"Chou, A.W., Ko, K.: On the complexity of finding paths in a two-dimensional domain I: shortest paths. Math. Log. Q. 50(6), 551\u2013572 (2004)","journal-title":"Math. Log. Q."},{"issue":"1\u20133","key":"4_CR7","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.tcs.2004.11.016","volume":"337","author":"AW Chou","year":"2005","unstructured":"Chou, A.W., Ko, K.: The computational complexity of distance functions of two-dimensional domains. Theor. Comput. Sci. 337(1\u20133), 360\u2013369 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.entcs.2004.06.033","volume":"120","author":"AW Chou","year":"2005","unstructured":"Chou, A.W., Ko, K.: On the complexity of finding paths in a two-dimensional domain II: piecewise straight-line paths. Electr. Notes Theor. Comput. Sci. 120, 45\u201357 (2005)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"issue":"3","key":"4_CR9","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1017\/S0305004100046867","volume":"69","author":"Roy O. Davies","year":"1971","unstructured":"Davies, R.O.: Some remarks on the Kakeya problem. In: Proceedings of the Cambridge Philosophical Society, vol. 69, pp. 417\u2013421 (1971)","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"53","DOI":"10.4064\/cm-42-1-53-58","volume":"42","author":"RO Davies","year":"1979","unstructured":"Davies, R.O.: Two counterexamples concerning Hausdorff dimensions of projections. Colloq. Math. 42, 53\u201358 (1979)","journal-title":"Colloq. Math."},{"key":"4_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3","volume-title":"Algorithmic Randomness and Complexity","author":"R Downey","year":"2010","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, New York (2010). \nhttps:\/\/doi.org\/10.1007\/978-0-387-68441-3"},{"key":"4_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-74749-1","volume-title":"Measure, Topology, and Fractal Geometry","author":"G Edgar","year":"2008","unstructured":"Edgar, G.: Measure, Topology, and Fractal Geometry, 2nd edn. Springer, New York (2008). \nhttps:\/\/doi.org\/10.1007\/978-0-387-74749-1","edition":"2"},{"key":"4_CR13","series-title":"Progress in Probability","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-18660-3_1","volume-title":"Fractal Geometry and Stochastics V","author":"K Falconer","year":"2015","unstructured":"Falconer, K., Fraser, J., Jin, X.: Sixty years of fractal projections. In: Bandt, C., Falconer, K., Z\u00e4hle, M. (eds.) Fractal Geometry and Stochastics V. PP, vol. 70, pp. 3\u201325. Springer, Cham (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-18660-3_1"},{"key":"4_CR14","volume-title":"Fractal Geometry: Mathematical Foundations and Applications","author":"KJ Falconer","year":"2014","unstructured":"Falconer, K.J.: Fractal Geometry: Mathematical Foundations and Applications, 3rd edn. Wiley, Hoboken (2014)","edition":"3"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01457179","volume":"79","author":"F Hausdorff","year":"1918","unstructured":"Hausdorff, F.: Dimension und \u00e4usseres Mass. Math. Ann. 79, 157\u2013179 (1918)","journal-title":"Math. Ann."},{"key":"4_CR16","unstructured":"Kahane, J.P.: Sur la dimension des intersections. In: Barroso, J.A. (ed.) Aspects of Mathematics and Its Applications, pp. 419\u2013430. Elsevier (1986). N.-Holl. Math. Libr. 34"},{"key":"4_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Complexity Theory of Real Functions","author":"K Ko","year":"1991","unstructured":"Ko, K.: Complexity Theory of Real Functions. Birkh\u00e4user, Boston (1991)"},{"issue":"1&2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0304-3975(94)00154-B","volume":"145","author":"K Ko","year":"1995","unstructured":"Ko, K.: A polynomial-time computable curve whose interior has a nonrecursive measure. Theor. Comput. Sci. 145(1&2), 241\u2013270 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"4_CR19","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0168-0072(97)00060-2","volume":"93","author":"K Ko","year":"1998","unstructured":"Ko, K.: On the computability of fractal dimensions and Hausdorff measure. Ann. Pure Appl. Logic 93(1\u20133), 195\u2013216 (1998)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"3\u20134","key":"4_CR20","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.jco.2013.03.002","volume":"29","author":"K Ko","year":"2013","unstructured":"Ko, K.: On the complexity of computing the Hausdorff distance. J. Complex. 29(3\u20134), 248\u2013262 (2013)","journal-title":"J. Complex."},{"key":"4_CR21","unstructured":"Ko, K., Weihrauch, K.: On the measure of two-dimensional regions with polynomial-time computable boundaries. In: Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, 24\u201327 May 1996, pp. 150\u2013159 (1996)"},{"issue":"1\u20133","key":"4_CR22","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2007.04.020","volume":"381","author":"K Ko","year":"2007","unstructured":"Ko, K., Yu, F.: Jordan curves with polynomial inverse moduli of continuity. Theor. Comput. Sci. 381(1\u20133), 148\u2013161 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"2008","unstructured":"Li, M., Vit\u00e1nyi, P.M.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, New York (2008). \nhttps:\/\/doi.org\/10.1007\/978-0-387-49820-1","edition":"3"},{"issue":"1","key":"4_CR24","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0890-5401(03)00187-1","volume":"187","author":"JH Lutz","year":"2003","unstructured":"Lutz, J.H.: The dimensions of individual strings and sequences. Inf. Comput. 187(1), 49\u201379 (2003)","journal-title":"Inf. Comput."},{"issue":"2","key":"4_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.3233\/COM-150038","volume":"4","author":"JH Lutz","year":"2015","unstructured":"Lutz, J.H., Lutz, N.: Lines missing every random point. Computability 4(2), 85\u2013102 (2015)","journal-title":"Computability"},{"issue":"2","key":"4_CR26","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/3201783","volume":"10","author":"JH Lutz","year":"2018","unstructured":"Lutz, J.H., Lutz, N.: Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Trans. Comput. Theory 10(2), 7:1\u20137:22 (2018)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"3","key":"4_CR27","doi-asserted-by":"publisher","first-page":"1080","DOI":"10.1137\/070684689","volume":"38","author":"JH Lutz","year":"2008","unstructured":"Lutz, J.H., Mayordomo, E.: Dimensions of points in self-similar fractals. SIAM J. Comput. 38(3), 1080\u20131112 (2008)","journal-title":"SIAM J. Comput."},{"key":"4_CR28","unstructured":"Lutz, N.: Fractal intersections and products via algorithmic dimension. In: 42nd Proceedings of the International Symposium on Mathematical Foundations of Computer Science, Aalborg, Denmark, 21\u201325 August 2017 (2017)"},{"key":"4_CR29","unstructured":"Lutz, N.: Fractal intersections and products via algorithmic dimension (extended version) (2019). \nhttps:\/\/arxiv.org\/abs\/1612.01659"},{"key":"4_CR30","unstructured":"Lutz, N., Stull, D.M.: Bounding the dimension of points on a line. Information and Computation (to appear)"},{"key":"4_CR31","unstructured":"Lutz, N., Stull, D.M.: Projection theorems using effective dimension. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, 27\u201331 August 2018, pp. 71:1\u201371:15 (2018)"},{"issue":"3","key":"4_CR32","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1112\/plms\/s3-4.1.257","volume":"4","author":"JM Marstrand","year":"1954","unstructured":"Marstrand, J.M.: Some fundamental geometrical properties of plane sets of fractional dimensions. Proc. Lond. Math. Soc. 4(3), 257\u2013302 (1954)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"6","key":"4_CR33","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Inf. Control 9(6), 602\u2013619 (1966)","journal-title":"Inf. Control"},{"key":"4_CR34","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF02392192","volume":"152","author":"P Mattila","year":"1984","unstructured":"Mattila, P.: Hausdorff dimension and capacities of intersections of sets in $$n$$-space. Acta Math. 152, 77\u2013105 (1984)","journal-title":"Acta Math."},{"key":"4_CR35","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1112\/S0025579300011001","volume":"32","author":"P Mattila","year":"1985","unstructured":"Mattila, P.: On the Hausdorff dimension and capacities of intersections. Mathematika 32, 213\u2013217 (1985)","journal-title":"Mathematika"},{"key":"4_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511623813","volume-title":"Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability","author":"P Mattila","year":"1995","unstructured":"Mattila, P.: Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability. Cambridge University Press, Cambridge (1995)"},{"issue":"1","key":"4_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(02)00343-5","volume":"84","author":"E Mayordomo","year":"2002","unstructured":"Mayordomo, E.: A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett. 84(1), 1\u20133 (2002)","journal-title":"Inf. Process. Lett."},{"key":"4_CR38","doi-asserted-by":"publisher","first-page":"2753","DOI":"10.1090\/S0002-9939-2011-11111-0","volume":"140","author":"U Molter","year":"2012","unstructured":"Molter, U., Rela, E.: Furstenberg sets for a fractal set of directions. Proc. Am. Math. Soc. 140, 2753\u20132765 (2012)","journal-title":"Proc. Am. Math. Soc."},{"key":"4_CR39","volume-title":"Descriptive Set Theory","author":"YN Moschovakis","year":"1980","unstructured":"Moschovakis, Y.N.: Descriptive Set Theory. North-Holland Publishing, Amsterdam (1980)"},{"key":"4_CR40","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001","volume-title":"Computability and Randomness","author":"A Nies","year":"2009","unstructured":"Nies, A.: Computability and Randomness. Oxford University Press Inc., New York (2009)"},{"key":"4_CR41","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/220","volume-title":"Kolmogorov Complexity and Algorithmic Randomness","author":"A Shen","year":"2017","unstructured":"Shen, A., Uspensky, V.A., Vereshchagin, N.: Kolmogorov Complexity and Algorithmic Randomness. AMS, Boston (2017)"},{"issue":"1\u20132","key":"4_CR42","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0304-3975(01)00035-4","volume":"271","author":"A Shen","year":"2002","unstructured":"Shen, A., Vereshchagin, N.K.: Logical operations and Kolmogorov complexity. Theoret. Comput. Sci. 271(1\u20132), 125\u2013129 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR43","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1016\/j.apal.2009.01.008","volume":"160","author":"RI Soare","year":"2009","unstructured":"Soare, R.I.: Turing oracle machines, online computing, and three displacements in computability theory. Ann. Pure Appl. Log. 160, 368\u2013399 (2009)","journal-title":"Ann. Pure Appl. Log."},{"key":"4_CR44","unstructured":"Stull, D.M.: Results on the dimension spectra of planar lines. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, 27\u201331 August 2018, pp. 79:1\u201379:15 (2018)"},{"issue":"1","key":"4_CR45","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF02392379","volume":"153","author":"D Sullivan","year":"1984","unstructured":"Sullivan, D.: Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups. Acta Math. 153(1), 259\u2013277 (1984)","journal-title":"Acta Math."},{"issue":"1","key":"4_CR46","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1017\/S0305004100059119","volume":"91","author":"C Tricot","year":"1982","unstructured":"Tricot, C.: Two definitions of fractional dimension. Math. Proc. Camb. Philos. Soc. 91(1), 57\u201374 (1982)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"issue":"3","key":"4_CR47","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1017\/S030500410007506X","volume":"120","author":"Y Xiao","year":"1996","unstructured":"Xiao, Y.: Packing dimension, Hausdorff dimension and Cartesian product sets. Math. Proc. Camb. Philos. Soc. 120(3), 535\u2013546 (1996)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"issue":"6","key":"4_CR48","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1016\/j.jco.2006.05.005","volume":"22","author":"F Yu","year":"2006","unstructured":"Yu, F., Chou, A.W., Ko, K.: On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain. J. Complex. 22(6), 803\u2013817 (2006)","journal-title":"J. Complex."}],"container-title":["Lecture Notes in Computer Science","Complexity and Approximation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-41672-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T02:03:50Z","timestamp":1582164230000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-41672-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030416713","9783030416720"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-41672-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"21 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}