101 citations · 688 across the 27 of their papers we have counts for
25 papers · 1 filter
Computability of the Hahn-Banach Theorem Revisited
Vasco Brattka, Christopher Sorg
Computational properties of the Hahn-Banach theorem have been studied in computable, constructive and reverse mathematics and in all these approaches the theorem is equivalent to w…
Uniform Computability of PAC Learning
Vasco Brattka, Guillaume Chirache
We study uniform computability properties of PAC learning using Weihrauch complexity. We focus on closed concept classes, which are either represented by positive, by negative or b…
Computable Bases
Vasco Brattka, Emmanuel Rauzy
In computable analysis typically topological spaces with countable bases are considered. The Theorem of Kreitz-Weihrauch implies that the subbase representation of a second-countab…
Effective bases and notions of effective second countability in computable analysis
Vasco Brattka, Emmanuel Rauzy
We investigate different notions of "computable topological base" for represented spaces. We show that several non-equivalent notions of bases become equivalent when we consider co…
Loops, Inverse Limits and Non-Determinism
Vasco Brattka
We introduce an operator on problems in Weihrauch complexity, which we call the infinite loop or inverse limit, and which corresponds to an infinite compositional product. This ope…
On the Complexity of Computing Gödel Numbers
Vasco Brattka
Given a computable sequence of natural numbers, it is a natural task to find a Gödel number of a program that generates this sequence. It is easy to see that this problem is neithe…
Weihrauch Complexity and the Hagen School of Computable Analysis
Vasco Brattka
Weihrauch complexity is now an established and active part of mathematical logic. It can be seen as a computability-theoretic approach to classifying the uniform computational cont…
Stashing And Parallelization Pentagons
Vasco Brattka
Parallelization is an algebraic operation that lifts problems to sequences in a natural way. Given a sequence as an instance of the parallelized problem, another sequence is a solu…
The Discontinuity Problem
Vasco Brattka
Matthias Schröder has asked the question whether there is a weakest discontinuous problem in the continuous version of the Weihrauch lattice. Such a problem can be considered as th…
Completion of Choice
Vasco Brattka, Guido Gherardi
We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal role in Weihrauch complexity. For one, they can be used as landma…
A Galois connection between Turing jumps and limits
Vasco Brattka
Limit computable functions can be characterized by Turing jumps on the input side or limits on the output side. As a monad of this pair of adjoint operations we obtain a problem th…
Weihrauch Complexity in Computable Analysis
Vasco Brattka, Guido Gherardi, Arno Pauly
We provide a self-contained introduction into Weihrauch complexity and its applications to computable analysis. This includes a survey on some classification results and a discussi…
The Vitali Covering Theorem in the Weihrauch Lattice
Vasco Brattka, Guido Gherardi, Rupert Hölzl +1
We study the uniform computational content of the Vitali Covering Theorem for intervals using the tool of Weihrauch reducibility. We show that a more detailed picture emerges than…
Computability and Analysis, a Historical Approach
Vasco Brattka
The history of computability theory and and the history of analysis are surprisingly intertwined since the beginning of the twentieth century. For one, Émil Borel discussed his ide…
On the Uniform Computational Content of the Baire Category Theorem
Vasco Brattka, Matthew Hendtlass, Alexander P. Kreuzer
We study the uniform computational content of different versions of the Baire Category Theorem in the Weihrauch lattice. The Baire Category Theorem can be seen as a pigeonhole prin…
On the Uniform Computational Content of Ramsey's Theorem
Vasco Brattka, Tahina Rakotoniaina
We study the uniform computational content of Ramsey's theorem in the Weihrauch lattice. Our central results provide information on how Ramsey's theorem behaves under product, para…
On the Uniform Computational Content of Computability Theory
Vasco Brattka, Matthew Hendtlass, Alexander P. Kreuzer
We demonstrate that the Weihrauch lattice can be used to classify the uniform computational content of computability-theoretic properties as well as the computational content of th…
Probabilistic Computability and Choice
Vasco Brattka, Guido Gherardi, Rupert Hölzl
We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-value…
Connected Choice and the Brouwer Fixed Point Theorem
Vasco Brattka, Stéphane Le Roux, Joseph S. Miller +1
We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed…
Computability and analysis: the legacy of Alan Turing
Jeremy Avigad, Vasco Brattka
We discuss the legacy of Alan Turing and his impact on computability and analysis.
Randomness and Differentiability
Vasco Brattka, Joseph S. Miller, André Nies
We characterize some major algorithmic randomness notions via differentiability of effective functions. (1) As the main result we show that a real number z in [0,1] is computably r…
The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
Vasco Brattka, Guido Gherardi, Alberto Marcone
We classify the computational content of the Bolzano-Weierstrass Theorem and variants thereof in the Weihrauch lattice. For this purpose we first introduce the concept of a derivat…
Closed Choice and a Uniform Low Basis Theorem
Vasco Brattka, Matthew de Brecht, Arno Pauly
We study closed choice principles for different spaces. Given information about what does not constitute a solution, closed choice determines a solution. We show that with closed c…
Effective Choice and Boundedness Principles in Computable Analysis
Vasco Brattka, Guido Gherardi
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 contin…