Stéphane Le Roux ; Arno Pauly - Finite choice, convex choice and finding roots

lmcs:1607 - Logical Methods in Computer Science, December 2, 2015, Volume 11, Issue 4 -
Finite choice, convex choice and finding roots

Authors: Stéphane Le Roux ; Arno Pauly ORCID-iD

    We investigate choice principles in the Weihrauch lattice for finite sets on the one hand, and convex sets on the other hand. Increasing cardinality and increasing dimension both correspond to increasing Weihrauch degrees. Moreover, we demonstrate that the dimension of convex sets can be characterized by the cardinality of finite sets encodable into them. Precisely, choice from an n+1 point set is reducible to choice from a convex set of dimension n, but not reducible to choice from a convex set of dimension n-1. Furthermore we consider searching for zeros of continuous functions. We provide an algorithm producing 3n real numbers containing all zeros of a continuous function with up to n local minima. This demonstrates that having finitely many zeros is a strictly weaker condition than having finitely many local extrema. We can prove 3n to be optimal.

    Volume: Volume 11, Issue 4
    Published on: December 2, 2015
    Submitted on: November 11, 2013
    Keywords: Mathematics - Logic,Computer Science - Computational Geometry
    Fundings :
      Source : OpenAIRE Research Graph
    • Computable Analysis; Funder: European Commission; Code: 294962

    Linked data

    Source : ScholeXplorer IsReferencedBy ARXIV 1206.4809
    Source : ScholeXplorer IsReferencedBy DOI 10.1142/s0219061319500041
    Source : ScholeXplorer IsReferencedBy DOI 10.48550/arxiv.1206.4809
    • 10.1142/s0219061319500041
    • 10.1142/s0219061319500041
    • 10.1142/s0219061319500041
    • 10.48550/arxiv.1206.4809
    • 1206.4809
    Connected choice and the Brouwer fixed point theorem
    Brattka, Vasco ; Roux, Stéphane Le ; Miller, Joseph S. ; Pauly, Arno ;

    10 Documents citing this article


    Consultation statistics

    This page has been seen 664 times.
    This article's PDF has been downloaded 243 times.