Search Results

Documents authored by Gherardi, Guido

Document
DOI: 10.4230/LIPIcs.STACS.2015.130
Las Vegas Computability and Algorithmic Randomness

Authors: Vasco Brattka, Guido Gherardi, and Rupert Hölzl

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In this article we try to formalize the question "What can be computed with access to randomness?" We propose the very fine-grained Weihrauch lattice as an approach to differentiate between different types of computation with access to randomness. In particular, we show that a natural concept of Las Vegas computability on infinite objects is more powerful than mere oracle access to a Martin-Löf random object. As a concrete problem that is Las Vegas computable but not computable with access to a Martin-Löf random oracle we study the problem of finding Nash equilibria.
Cite as

Vasco Brattka, Guido Gherardi, and Rupert Hölzl. Las Vegas Computability and Algorithmic Randomness. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 130-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{brattka_et_al:LIPIcs.STACS.2015.130,
  author =	{Brattka, Vasco and Gherardi, Guido and H\"{o}lzl, Rupert},
  title =	{{Las Vegas Computability and Algorithmic Randomness}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{130--142},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.130},
  URN =		{urn:nbn:de:0030-drops-49093},
  doi =		{10.4230/LIPIcs.STACS.2015.130},
  annote =	{Keywords: Weihrauch degrees, weak weak K\"{o}nig's lemma, Las Vegas computability, algorithmic randomness, Nash equilibria}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2261
Weihrauch Degrees, Omniscience Principles and Weak Computability

Authors: Vasco Brattka and Guido Gherardi

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension of this reducibility for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice with the disjoint union of multi-valued functions as greatest lower bound operation. We show that parallelization is a closure operator for this semi-lattice and the parallelized Weihrauch degrees even form a lattice with the product of multi-valued functions as greatest lower bound operation. We show that the Medvedev lattice and hence the Turing upper semi-lattice can both be embedded into the parallelized Weihrauch lattice in a natural way. The importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. This allows a new purely topological or computational approach to metamathematics that sheds new light on the nature of theorems. As crucial corner points of this classification scheme we study the limited principle of omniscience $\LPO$, the lesser limited principle of omniscience $\LLPO$ and their parallelizations. We show that parallelized $\LLPO$ is equivalent to Weak König's Lemma and hence to the Hahn-Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized $\LLPO$ and we present a new proof that the class of weakly computable operations is closed under composition. This proof is based on a computational version of Kleene's ternary logic. Moreover, we characterize weakly computable operations on computable metric spaces as operations that admit upper semi-computable compact-valued selectors and we show that any single-valued weakly computable operation is already computable in the ordinary sense.
Cite as

Vasco Brattka and Guido Gherardi. Weihrauch Degrees, Omniscience Principles and Weak Computability. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 83-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brattka_et_al:OASIcs.CCA.2009.2261,
  author =	{Brattka, Vasco and Gherardi, Guido},
  title =	{{Weihrauch Degrees, Omniscience Principles and Weak Computability}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{83--94},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2261},
  URN =		{urn:nbn:de:0030-drops-22617},
  doi =		{10.4230/OASIcs.CCA.2009.2261},
  annote =	{Keywords: Computable analysis, constructive analysis, reverse mathematics, effective descriptive set theory}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2262
Effective Choice and Boundedness Principles in Computable Analysis

Authors: Vasco Brattka and Guido Gherardi

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified certain choice principles on closed sets which are cornerstones among Weihrauch degrees and it turns out that certain core theorems in analysis can be classified naturally in this structure. In particular, we study theorems such as the Intermediate Value Theorem, the Baire Category Theorem, the Banach Inverse Mapping Theorem, the Closed Graph Theorem and the Uniform Boundedness Theorem. Well-known omniscience principles from constructive mathematics such as $\LPO$ and $\LLPO$ can naturally be considered as Weihrauch degrees and they play an important role in our classification. Our classification scheme does not require any particular logical framework or axiomatic setting, but it can be carried out in the framework of classical mathematics using tools of topology, computability theory and computable analysis. Finally, we present a number of metatheorems that allow to derive upper bounds for the classification of the Weihrauch degree of many theorems and we discuss the Brouwer Fixed Point Theorem as an example.
Cite as

Vasco Brattka and Guido Gherardi. Effective Choice and Boundedness Principles in Computable Analysis. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 95-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brattka_et_al:OASIcs.CCA.2009.2262,
  author =	{Brattka, Vasco and Gherardi, Guido},
  title =	{{Effective Choice and Boundedness Principles in Computable Analysis}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{95--106},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2262},
  URN =		{urn:nbn:de:0030-drops-22629},
  doi =		{10.4230/OASIcs.CCA.2009.2262},
  annote =	{Keywords: Computable analysis, constructive analysis, reverse mathematics, effective descriptive set theory}
}
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