2 Search Results for "Wright, Matthew L."

Document
DOI: 10.4230/LIPIcs.STACS.2022.8
Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order

Authors: Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski

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

Abstract
The intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum - the set of Turing degrees of images of the relation in all computable isomorphic copies of that structure. We investigate the intrinsic complexity of unary total recursive functions on nonnegative integers with standard order. According to existing results, the possible spectra of such functions include three sets consisting of precisely: the computable degree, all c.e. degrees and all Δ₂ degrees. These results, however, fall far short of the full classification. In this paper, we obtain a more complete picture by giving a few criteria for a function to have intrinsic complexity equal to one of the three candidate sets of degrees. Our investigations are based on the notion of block functions and a broader class of quasi-block functions beyond which all functions of interest have intrinsic complexity equal to the c.e. degrees. We also answer the questions raised by Wright [Wright, 2018] and Harrison-Trainor [Harrison-Trainor, 2018] by showing that the division between computable, c.e. and Δ₂ degrees is insufficient in this context as there is a unary total recursive function whose spectrum contains all c.e. degrees but is strictly contained in the Δ₂ degrees.
Cite as

Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski. Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bazhenov_et_al:LIPIcs.STACS.2022.8,
  author =	{Bazhenov, Nikolay and Kaloci\'{n}ski, Dariusz and Wroc{\l}awski, Micha{\l}},
  title =	{{Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{8:1--8:20},
  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.8},
  URN =		{urn:nbn:de:0030-drops-158185},
  doi =		{10.4230/LIPIcs.STACS.2022.8},
  annote =	{Keywords: Computable Structure Theory, Degree Spectra, \omega-Type Order, c.e. Degrees, d.c.e. Degrees, \Delta₂ Degrees, Learnability}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.72
Introduction to Persistent Homology

Authors: Matthew L. Wright

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
This video presents an introduction to persistent homology, aimed at a viewer who has mathematical aptitude but not necessarily knowledge of algebraic topology. Persistent homology is an algebraic method of discerning the topological features of complex data, which in recent years has found applications in fields such as image processing and biological systems. Using smooth animations, the video conveys the intuition behind persistent homology, while giving a taste of its key properties, applications, and mathematical underpinnings.
Cite as

Matthew L. Wright. Introduction to Persistent Homology. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 72:1-72:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{wright:LIPIcs.SoCG.2016.72,
  author =	{Wright, Matthew L.},
  title =	{{Introduction to Persistent Homology}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{72:1--72:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.72},
  URN =		{urn:nbn:de:0030-drops-59643},
  doi =		{10.4230/LIPIcs.SoCG.2016.72},
  annote =	{Keywords: Persistent Homology, Topological Data Analysi}
}
  • Refine by Author
  • 1 Bazhenov, Nikolay
  • 1 Kalociński, Dariusz
  • 1 Wright, Matthew L.
  • 1 Wrocławski, Michał

  • Refine by Classification
  • 1 Theory of computation → Computability

  • Refine by Keyword
  • 1 Computable Structure Theory
  • 1 Degree Spectra
  • 1 Learnability
  • 1 Persistent Homology
  • 1 Topological Data Analysi
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2022

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