Found 3 Possible Name Variants:

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

**Published in:** LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Let L_{a,b} be a line in the Euclidean plane with slope a and intercept b. The dimension spectrum sp(L_{a,b}) is the set of all effective dimensions of individual points on L_{a,b}. Jack Lutz, in the early 2000s posed the dimension spectrum conjecture. This conjecture states that, for every line L_{a,b}, the spectrum of L_{a,b} contains a unit interval.
In this paper we prove that the dimension spectrum conjecture is true. Specifically, let (a,b) be a slope-intercept pair, and let d = min{dim(a,b), 1}. For every s ∈ [0, 1], we construct a point x such that dim(x, ax + b) = d + s. Thus, we show that sp(L_{a,b}) contains the interval [d, 1+ d].

D. M. Stull. The Dimension Spectrum Conjecture for Planar Lines. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 133:1-133:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{stull:LIPIcs.ICALP.2022.133, author = {Stull, D. M.}, title = {{The Dimension Spectrum Conjecture for Planar Lines}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {133:1--133:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.133}, URN = {urn:nbn:de:0030-drops-164749}, doi = {10.4230/LIPIcs.ICALP.2022.133}, annote = {Keywords: Algorithmic randomness, Kolmogorov complexity, effective dimension} }

Document

**Published in:** LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

The point-to-set principle [Lutz and Lutz, 2018] characterizes the Hausdorff dimension of a subset E ⊆ ℝⁿ by the effective (or algorithmic) dimension of its individual points. This characterization has been used to prove several results in classical, i.e., without any computability requirements, analysis. Recent work has shown that algorithmic techniques can be fruitfully applied to Marstrand’s projection theorem, a fundamental result in fractal geometry.
In this paper, we introduce an extension of point-to-set principle - the notion of optimal oracles for subsets E ⊆ ℝⁿ. One of the primary motivations of this definition is that, if E has optimal oracles, then the conclusion of Marstrand’s projection theorem holds for E. We show that every analytic set has optimal oracles. We also prove that if the Hausdorff and packing dimensions of E agree, then E has optimal oracles. Moreover, we show that the existence of sufficiently nice outer measures on E implies the existence of optimal Hausdorff oracles. In particular, the existence of exact gauge functions for a set E is sufficient for the existence of optimal Hausdorff oracles, and is therefore sufficient for Marstrand’s theorem. Thus, the existence of optimal oracles extends the currently known sufficient conditions for Marstrand’s theorem to hold.
Under certain assumptions, every set has optimal oracles. However, assuming the axiom of choice and the continuum hypothesis, we construct sets which do not have optimal oracles. This construction naturally leads to a generalization of Davies' theorem on projections.

D. M. Stull. Optimal Oracles for Point-To-Set Principles. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{stull:LIPIcs.STACS.2022.57, author = {Stull, D. M.}, title = {{Optimal Oracles for Point-To-Set Principles}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {57:1--57:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.57}, URN = {urn:nbn:de:0030-drops-158675}, doi = {10.4230/LIPIcs.STACS.2022.57}, annote = {Keywords: Algorithmic randomness, Kolmogorov complexity, geometric measure theory} }

Document

**Published in:** LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

The Schnorr-Stimm dichotomy theorem [Schnorr and Stimm, 1972] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S, the following two things are true.
(1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S.
(2) If S is normal, then any finite-state gambler betting on S loses money at an exponential rate betting on S.
In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence div(S||α) of a probability measure α on Σ from a sequence S over Σ and the upper asymptotic divergence Div(S||α) of α from S in such a way that a sequence S is α-normal (meaning that every string w has asymptotic frequency α(w) in S) if and only if Div(S||α)=0. We also use the Kullback-Leibler divergence to quantify the total risk Risk_G(w) that a finite-state gambler G takes when betting along a prefix w of S.
Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to α-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes w of S.
(1') The infinitely-often exponential rate of winning in 1 is 2^{Div(S||α)|w|}.
(2') The exponential rate of loss in 2 is 2^{-Risk_G(w)}.
We also use (1') to show that 1-Div(S||α)/c, where c= log(1/ min_{a∈Σ} α(a)), is an upper bound on the finite-state α-dimension of S and prove the dual fact that 1-div(S||α)/c is an upper bound on the finite-state strong α-dimension of S.

Xiang Huang, Jack H. Lutz, Elvira Mayordomo, and Donald M. Stull. Asymptotic Divergences and Strong Dichotomy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.STACS.2020.51, author = {Huang, Xiang and Lutz, Jack H. and Mayordomo, Elvira and Stull, Donald M.}, title = {{Asymptotic Divergences and Strong Dichotomy}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {51:1--51:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.51}, URN = {urn:nbn:de:0030-drops-119125}, doi = {10.4230/LIPIcs.STACS.2020.51}, annote = {Keywords: finite-state dimension, finite-state gambler, Kullback-Leibler divergence, normal sequences} }

Document

**Published in:** LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

We introduce the notion of a semicomputable point in R^n, defined as a point having left-c.e. projections. We study the range of such a point, which is the set of directions on which its projections are left-c.e., and is a convex cone. We provide a thorough study of these notions, proving along the way new results on the computability of convex sets. We prove realization results, by identifying computability properties of convex cones that make them ranges of semicomputable points. We give two applications of the theory. The first one provides a better understanding of the Solovay derivatives. The second one is the investigation of left-c.e. quadratic polynomials. We show that this is, in fact, a particular case of the general theory of semicomputable points.

Mathieu Hoyrup and Donald M. Stull. Semicomputable Points in Euclidean Spaces. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hoyrup_et_al:LIPIcs.MFCS.2019.48, author = {Hoyrup, Mathieu and Stull, Donald M.}, title = {{Semicomputable Points in Euclidean Spaces}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {48:1--48:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.48}, URN = {urn:nbn:de:0030-drops-109928}, doi = {10.4230/LIPIcs.MFCS.2019.48}, annote = {Keywords: Semicomputable point, Left-c.e. real, Convex cone, Solovay reducibility, Genericity} }

Document

**Published in:** LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theorem, which shows that for every analytic set E, for almost every line L, the Hausdorff dimension of the orthogonal projection of E onto L is maximal.
We use Kolmogorov complexity to give two new results on the Hausdorff and packing dimensions of orthogonal projections onto lines. The first shows that the conclusion of Marstrand's theorem holds whenever the Hausdorff and packing dimensions agree on the set E, even if E is not analytic. Our second result gives a lower bound on the packing dimension of projections of arbitrary sets. Finally, we give a new proof of Marstrand's theorem using the theory of computing.

Neil Lutz and Donald M. Stull. Projection Theorems Using Effective Dimension. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.MFCS.2018.71, author = {Lutz, Neil and Stull, Donald M.}, title = {{Projection Theorems Using Effective Dimension}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {71:1--71:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.71}, URN = {urn:nbn:de:0030-drops-96532}, doi = {10.4230/LIPIcs.MFCS.2018.71}, annote = {Keywords: algorithmic randomness, geometric measure theory, Hausdorff dimension, Kolmogorov complexity} }

Document

**Published in:** LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

In this paper we investigate the (effective) dimension spectra of lines in the Euclidean plane. The dimension spectrum of a line L_{a,b}, sp(L), with slope a and intercept b is the set of all effective dimensions of the points (x, ax + b) on L. It has been recently shown that, for every a and b with effective dimension less than 1, the dimension spectrum of L_{a,b} contains an interval. Our first main theorem shows that this holds for every line. Moreover, when the effective dimension of a and b is at least 1, sp(L) contains a unit interval.
Our second main theorem gives lower bounds on the dimension spectra of lines. In particular, we show that for every alpha in [0,1], with the exception of a set of Hausdorff dimension at most alpha, the effective dimension of (x, ax + b) is at least alpha + dim(a,b)/2. As a consequence of this theorem, using a recent characterization of Hausdorff dimension using effective dimension, we give a new proof of a result by Molter and Rela on the Hausdorff dimension of Furstenberg sets.

Donald M. Stull. Results on the Dimension Spectra of Planar Lines. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 79:1-79:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{stull:LIPIcs.MFCS.2018.79, author = {Stull, Donald M.}, title = {{Results on the Dimension Spectra of Planar Lines}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {79:1--79:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.79}, URN = {urn:nbn:de:0030-drops-96611}, doi = {10.4230/LIPIcs.MFCS.2018.79}, annote = {Keywords: algorithmic randomness, geometric measure theory, Hausdorff dimension, Kolmogorov complexity} }

Document

**Published in:** LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

We study the interaction between polynomial space randomness and a fundamental result of analysis, the Lebesgue differentiation theorem. We generalize Ko's framework for polynomial space computability in R^n to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem characterizes weakly pspace random points. That is, a point x is weakly pspace random if and only if the Lebesgue differentiation theorem holds for a point x for every pspace L_1-computable function.

Xiang Huang and Donald M. Stull. Polynomial Space Randomness in Analysis. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 86:1-86:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.MFCS.2016.86, author = {Huang, Xiang and Stull, Donald M.}, title = {{Polynomial Space Randomness in Analysis}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {86:1--86:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.86}, URN = {urn:nbn:de:0030-drops-64943}, doi = {10.4230/LIPIcs.MFCS.2016.86}, annote = {Keywords: algorithmic randomness, computable analysis, resource-bounded randomness, complexity theory} }

Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Computability and semicomputability of compact subsets of the Euclidean spaces are important notions, that have been investigated for many classes of sets including fractals (Julia sets, Mandelbrot set) and objects with geometrical or topological constraints (embedding of a sphere). In this paper we investigate one of the simplest classes, namely the filled triangles in the plane. We study the properties of the parameters of semicomputable triangles, such as the coordinates of their vertices. This problem is surprisingly rich. We introduce and develop a notion of semicomputability of points of the plane which is a generalization in dimension 2 of the left-c.e. and right-c.e. numbers. We relate this notion to Solovay reducibility. We show that semicomputable triangles admit no finite parametrization, for some notion of parametrization.

Mathieu Hoyrup, Diego Nava Saucedo, and Don M. Stull. Semicomputable Geometry. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 129:1-129:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hoyrup_et_al:LIPIcs.ICALP.2018.129, author = {Hoyrup, Mathieu and Nava Saucedo, Diego and Stull, Don M.}, title = {{Semicomputable Geometry}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {129:1--129:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.129}, URN = {urn:nbn:de:0030-drops-91336}, doi = {10.4230/LIPIcs.ICALP.2018.129}, annote = {Keywords: Computable set, Semicomputable set, Solovay reducibility, Left-ce real, Genericity} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail