3 Search Results for "Stull, D. M."

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.133
The Dimension Spectrum Conjecture for Planar Lines

Authors: D. M. Stull

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

Abstract
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].
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.STACS.2022.57
Optimal Oracles for Point-To-Set Principles

Authors: D. M. Stull

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.ICALP.2018.129
Semicomputable Geometry

Authors: Mathieu Hoyrup, Diego Nava Saucedo, and Don M. Stull

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

Abstract
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.
Cite as

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-dev.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}
}
  • Refine by Author
  • 2 Stull, D. M.
  • 1 Hoyrup, Mathieu
  • 1 Nava Saucedo, Diego
  • 1 Stull, Don M.

  • Refine by Classification
  • 2 Theory of computation
  • 1 Theory of computation → Computability

  • Refine by Keyword
  • 2 Algorithmic randomness
  • 2 Kolmogorov complexity
  • 1 Computable set
  • 1 Genericity
  • 1 Left-ce real
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2022
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact