101 citations · 491 across the 53 of their papers we have counts for
17 papers · 1 filter
Embeddability of graphs and Weihrauch degrees
Vittorio Cipriani, Arno Pauly
We study the complexity of the following related computational tasks concerning a fixed countable graph G: 1. Does a countable graph H provided as input have a(n induced) subgraph…
Finding descending sequences through ill-founded linear orders
Jun Le Goh, Arno Pauly, Manlio Valenti
In this work we investigate the Weihrauch degree of the problem of finding an infinite descending sequence through a given ill-founded linear order, which is shared b…
Luzin's (N) and randomness reflection
Arno Pauly, Linda Westrick, Liang Yu
We show that a computable function has Luzin's property (N) if and only if it reflects -randomnes, if and only if it reflects $Δ^1_1(\mathc…
The open and clopen Ramsey theorems in the Weihrauch lattice
Alberto Marcone, Manlio Valenti
We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to from the…
Convex choice, finite choice and sorting
Takayuki Kihara, Arno Pauly
We study the Weihrauch degrees of closed choice for finite sets, closed choice for convex sets and sorting infinite sequences over finite alphabets. Our main results are: One, that…
Overt choice
Matthew de Brecht, Arno Pauly, Matthias Schröder
We introduce and study the notion of overt choice for countably-based spaces and for CoPolish spaces. Overt choice is the task of producing a point in a closed set specified by wha…