BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Arno Pauly

Arno Pauly appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer Sciencemath.LOComputer Science and Game TheoryComputational Complexitymath.GNMachine Learningmath.CTmath.PRMultiagent Systems

Catalog footprint

What is connected

27works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2021arXiv

A Computability Perspective on (Verified) Machine Learning

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 from the (unexpected?) perspective of computable analysis. This allows us to define the computational tasks underlying verified ML in a model-agnostic way, and show that they are in principle computable.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Adaptive Neighbourhoods for the Discovery of Adversarial Examples

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 caught the attention of the community. Many existing works have proposed methods for searching for adversarial examples within fixed-sized regions around training points. Our work complements and improves these existing approaches by adapting the size of these regions based on the problem complexity and data sampling density. This makes such approaches more appropriate for other types of data and may further improve adversarial training methods by increasing the region sizes without creating incorrect labels.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Enumeration degrees and non-metrizable topology

The enumeration degrees of sets of natural numbers can be identified with the degrees of difficulty of enumerating neighborhood bases of points in a universal second-countable $T_0$-space (e.g. the $ω$-power of the Sierpiński space). Hence, every represented second-countable $T_0$-space determines a collection of enumeration degrees. For instance, Cantor space captures the total degrees, and the Hilbert cube captures the continuous degrees by definition. Based on these observations, we utilize general topology (particularly non-metrizable topology) to establish a classification theory of enumeration degrees of sets of natural numbers.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Connected Choice and the Brouwer Fixed Point Theorem

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 set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the same dimension. Another main result is that connected choice is complete for dimension greater than or equal to two in the sense that it is computably equivalent to Weak Kőnig's Lemma. While we can present two independent proofs for dimension three and upwards that are either based on a simple geometric construction or a combinatorial argument, the proof for dimension two is based on a more involved inverse limit construction. The connected choice operation in dimension one is known to be equivalent to the Intermediate Value Theorem; we prove that this problem is not idempotent in contrast to the case of dimension two and upwards. We also prove that Lipschitz continuity with Lipschitz constants strictly larger than one does not simplify finding fixed points. Finally, we prove that finding a connectedness component of a closed subset of the Euclidean unit cube of any dimension greater or equal to one is equivalent to Weak Kőnig's Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract)

We consider a dynamical approach to sequential games. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and we show that in finite games the corresponding restriction of better-response dynamics will converge to a Nash equilibrium in quadratic time. Convergence happens on a per-player basis, and even in the presence of players with cyclic preferences, the players with acyclic preferences will stabilize. Thus, we obtain a candidate notion for rationality in the presence of irrational agents. Moreover, the restriction of convertibility can be justified by a conservative updating of beliefs about the other players strategies. For infinite sequential games we can retain convergence to a Nash equilibrium (in some sense), if the preferences are given by continuous payoff functions; or obtain a transfinite convergence if the outcome sets of the game are Delta^0_2 sets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Dividing by zero - how bad is it, really?

In computable analysis testing a real number for being zero is a fundamental example of a non-computable task. This causes problems for division: We cannot ensure that the number we want to divide by is not zero. In many cases, any real number would be an acceptable outcome if the divisor is zero - but even this cannot be done in a computable way. In this note we investigate the strength of the computational problem "Robust division": Given a pair of real numbers, the first not greater than the other, output their quotient if well-defined and any real number else. The formal framework is provided by Weihrauch reducibility. One particular result is that having later calls to the problem depending on the outcomes of earlier ones is strictly more powerful than performing all calls concurrently. However, having a nesting depths of two already provides the full power. This solves an open problem raised at a recent Dagstuhl meeting on Weihrauch reducibility. As application for "Robust division", we show that it suffices to execute Gaussian elimination.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Equilibria in multi-player multi-outcome infinite sequential games

We investigate the existence of certain types of equilibria (Nash, $\varepsilon$-Nash, subgame perfect, $\varepsilon$-subgame perfect, Pareto-optimal) in multi-player multi-outcome infinite sequential games. We use two fundamental approaches: one requires strong topological restrictions on the games, but produces very strong existence results. The other merely requires some very basic determinacy properties to still obtain some existence results. Both results are transfer results: starting with the existence of some equilibria for a small class of games, they allow us to conclude the existence of some type of equilibria for a larger class. To make the abstract results more concrete, we investigate as a special case infinite sequential games with real-valued payoff functions. Depending on the class of payoff functions (continuous, upper semi-continuous, Borel) and whether the game is zero-sum, we obtain various existence results for equilibria. Our results hold for games with two or up to countably many players.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Extending Finite Memory Determinacy to Multiplayer Games

We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. We provide a number of example that separate the various criteria we explore. Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant Nash equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Extending Finite Memory Determinacy to Multiplayer Games

We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. For most of our conditions we provide counterexamples showing that they cannot be dispensed with. Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant winning strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Minkowski games

We introduce and study Minkowski games. These are two player games, where the players take turns to chose positions in $\mathbb{R}^d$ based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded, and the other wants to escape to infinity; as well as safety games, where one player wants to stay within a prescribed set, while the other wants to leave it. We provide some general characterizations of which player can win such games, and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A comparison of concepts from computable analysis and effective descriptive set theory

Computable analysis and effective descriptive set theory are both concerned with complete metric spaces, functions between them and subsets thereof in an effective setting. The precise relationship of the various definitions used in the two disciplines has so far been neglected, a situation this paper is meant to remedy. As the role of the Cauchy completion is relevant for both effective approaches to Polish spaces, we consider the interplay of effectivity and completion in some more detail.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Function spaces for second-order polynomial time

In the context of second-order polynomial-time computability, we prove that there is no general function space construction. We proceed to identify restrictions on the domain or the codomain that do provide a function space with polynomial-time function evaluation containing all polynomial-time computable functions of that type. As side results we show that a polynomial-time counterpart to admissibility of a representation is not a suitable criterion for natural representations, and that the Weihrauch degrees embed into the polynomial-time Weihrauch degrees.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Many-one reductions and the category of multivalued functions

Multi-valued functions are common in computable analysis (built upon the Type 2 Theory of Effectivity), and have made an appearance in complexity theory under the moniker search problems leading to complexity classes such as PPAD and PLS being studied. However, a systematic investigation of the resulting degree structures has only been initiated in the former situation so far (the Weihrauch-degrees). A more general understanding is possible, if the category-theoretic properties of multi-valued functions are taken into account. In the present paper, the category-theoretic framework is established, and it is demonstrated that many-one degrees of multi-valued functions form a distributive lattice under very general conditions, regardless of the actual reducibility notions used (e.g. Cook, Karp, Weihrauch). Beyond this, an abundance of open questions arises. Some classic results for reductions between functions carry over to multi-valued functions, but others do not. The basic theme here again depends on category-theoretic differences between functions and multi-valued functions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the topological aspects of the theory of represented spaces

Represented spaces form the general setting for the study of computability derived from Turing machines. As such, they are the basic entities for endeavors such as computable analysis or computable measure theory. The theory of represented spaces is well-known to exhibit a strong topological flavour. We present an abstract and very succinct introduction to the field; drawing heavily on prior work by Escardó, Schröder, and others. Central aspects of the theory are function spaces and various spaces of subsets derived from other represented spaces, and -- closely linked to these -- properties of represented spaces such as compactness, overtness and separation principles. Both the derived spaces and the properties are introduced by demanding the computability of certain mappings, and it is demonstrated that typically various interesting mappings induce the same property.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Weihrauch degrees of finding equilibria in sequential games

We consider the degrees of non-computability (Weihrauch degrees) of finding winning strategies (or more generally, Nash equilibria) in infinite sequential games with certain winning sets (or more generally, outcome sets). In particular, we show that as the complexity of the winning sets increases in the difference hierarchy, the complexity of constructing winning strategies increases in the effective Borel hierarchy.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Relative Computability and Uniform Continuity of Relations

A type-2 computable real function is necessarily continuous; and this remains true for relative, i.e. oracle-based computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f:[0,1]->R is computable relative to some oracle. In their search for a similar topological characterization of relatively computable multivalued functions f:[0,1]=>R (aka relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than relative computability) and strong continuity (which is stronger than relative computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y in f(x), new ways of (linearly) ordering quantifiers arise, yet none of them turn out as satisfactory. We are thus led to a notion of uniform continuity based on the Henkin Quantifier; and prove it necessary for relative computability. In fact iterating this condition yields a strict hierarchy of notions each necessary, and the omega-th level also sufficient, for relative computability.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Closed Choice and a Uniform Low Basis Theorem

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 choice one can characterize several models of hypercomputation in a uniform framework using Weihrauch reducibility. The classes of functions which are reducible to closed choice of the singleton space, of the natural numbers, of Cantor space and of Baire space correspond to the class of computable functions, of functions computable with finitely many mind changes, of weakly computable functions and of effectively Borel measurable functions, respectively. We also prove that all these classes correspond to classes of non-deterministically computable functions with the respective spaces as advice spaces. Moreover, we prove that closed choice on Euclidean space can be considered as "locally compact choice" and it is obtained as product of closed choice on the natural numbers and on Cantor space. We also prove a Quotient Theorem for compact choice which shows that single-valued functions can be "divided" by compact choice in a certain sense. Another result is the Independent Choice Theorem, which provides a uniform proof that many choice principles are closed under composition. Finally, we also study the related class of low computable functions, which contains the class of weakly computable functions as well as the class of functions computable with finitely many mind changes. As one main result we prove a uniform version of the Low Basis Theorem that states that closed choice on Cantor space (and the Euclidean space) is low computable. We close with some related observations on the Turing jump operation and its initial topology.

0 citations0 reviewsNo code linkedOpen access