Zobrazeno 1 - 10
of 232
pro vyhledávání: '"PAULY, ARNO"'
Autor:
Pauly, Arno
We study the complexity of the computational task ``Given a colouring $c : \mathbb{Q} \to \mathbf{k}$, find a monochromatic $S \subseteq \mathbb{Q}$ such that $(S,<) \cong (\mathbb{Q},<)$''. The framework is Weihrauch reducibility. Our results answer
Externí odkaz:
http://arxiv.org/abs/2407.03722
We study the equational theory of the Weihrauch lattice with multiplication, meaning the collection of equations between terms built from variables, the lattice operations $\sqcup$, $\sqcap$, the product $\times$, and the finite parallelization $(-)^
Externí odkaz:
http://arxiv.org/abs/2403.13975
Autor:
Pauly, Arno, Soldà, Giovanni
We explore the low levels of the structure of the continuous Weihrauch degrees of first-order problems. In particular, we show that there exists a minimal discontinuous first-order degree, namely that of $\accn$, without any determinacy assumptions.
Externí odkaz:
http://arxiv.org/abs/2401.12641
We explore the Weihrauch degree of the problems ``find a bad sequence in a non-well quasi order'' ($\mathsf{BS}$) and ``find a descending sequence in an ill-founded linear order'' ($\mathsf{DS}$). We prove that $\mathsf{DS}$ is strictly Weihrauch red
Externí odkaz:
http://arxiv.org/abs/2401.11807
Publikováno v:
Proceedings of the American Mathematical Society 152 (2024), no. 11, 4893--4901
In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem $f$ is a minimal cover or strong minimal cover of a problem $h$. We show that strong minimal covers only exist
Externí odkaz:
http://arxiv.org/abs/2311.12676
Autor:
Cipriani, Vittorio, Pauly, Arno
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 isomorphic to G? 2. Given a countable graph H that has a(n induced) su
Externí odkaz:
http://arxiv.org/abs/2305.00935
We characterize the strength, in terms of Weihrauch degrees, of certain problems related to Ramsey-like theorems concerning colourings of the rationals and of the natural numbers. The theorems we are chiefly interested in assert the existence of almo
Externí odkaz:
http://arxiv.org/abs/2301.02833
Autor:
Pauly, Arno1 (AUTHOR) arno.m.pauly@gmail.com, Pradic, Cécilia1 (AUTHOR) c.pradic@swansea.ac.uk, Soldà, Giovanni2 (AUTHOR) giovanni.a.solda@gmail.com
Publikováno v:
Computability. 2024, Vol. 13 Issue 3/4, p459-483. 25p.
Autor:
Crook, Tonicha, Pauly, Arno
Is there an algorithm that takes a game in normal form as input, and outputs a Nash equilibrium? If the payoffs are integers, the answer is yes, and lot of work has been done in its computational complexity. If the payoffs are permitted to be real nu
Externí odkaz:
http://arxiv.org/abs/2109.00972
There is a strong consensus that combining the versatility of machine learning with the assurances given by formal verification is highly desirable. It is much less clear what verified machine learning should mean exactly. We consider this question f
Externí odkaz:
http://arxiv.org/abs/2102.06585