101 citations · 491 across the 53 of their papers we have counts for
9 papers · 1 filter
How constructive is constructing measures?
Arno Pauly, Willem L. Fouché
Given some set, how hard is it to construct a measure supported by it? We classify some variations of this task in the Weihrauch lattice. Particular attention is paid to Frostman m…
The descriptive theory of represented spaces
Arno Pauly
This is a survey on the ongoing development of a descriptive theory of represented spaces, which is intended as an extension of both classical and effective descriptive set theory…
Weihrauch degrees of finding equilibria in sequential games
Stephane Le Roux, Arno Pauly
We consider the degrees of non-computability (Weihrauch degrees) of finding winning strategies (or more generally, Nash equilibria) in infinite sequential games with certain winnin…
Point degree spectra of represented spaces
Takayuki Kihara, Arno Pauly
We introduce the point degree spectrum of a represented space as a substructure of the Medvedev degrees, which integrates the notion of Turing degrees, enumeration degrees, continu…
Efficient Decomposition of Bimatrix Games (Extended Abstract)
Xiang Jiang, Arno Pauly
Exploiting the algebraic structure of the set of bimatrix games, a divide-and-conquer algorithm for finding Nash equilibria is proposed. The algorithm is fixed-parameter tractable…
Non-deterministic computation and the Jayne-Rogers Theorem
Arno Pauly, Matthew de Brecht
We provide a simple proof of a computable analogue to the Jayne Rogers Theorem from descriptive set theory. The difficulty of the proof is delegated to a simulation result pertaini…