101 citations · 491 across the 53 of their papers we have counts for
60 papers
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…
The Weihrauch degree of finding Nash equilibria in multiplayer games
Tonicha Crook, Arno Pauly
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 it…
A Computability Perspective on (Verified) Machine Learning
Tonicha Crook, Jay Morgan, Arno Pauly +1
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 veri…
Adaptive Neighbourhoods for the Discovery of Adversarial Examples
Jay Morgan, Adeline Paiement, Arno Pauly +1
Deep Neural Networks (DNNs) have often supplied state-of-the-art results in pattern recognition tasks. Despite their advances, however, the existence of adversarial examples have c…
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…
An update on Weihrauch complexity, and some open questions
Arno Pauly
This is an informal survey of progress in Weihrauch complexity (cf arXiv:1707.03202) in the period 2018-2020. Open questions are emphasised.