---
res:
bibo_abstract:
- 'We study the problem of robust satisfiability of systems of nonlinear equations,
namely, whether for a given continuous function f:K→ ℝn on a finite simplicial
complex K and α > 0, it holds that each function g: K → ℝn such that ||g -
f || ∞ < α, has a root in K. Via a reduction to the extension problem of maps
into a sphere, we particularly show that this problem is decidable in polynomial
time for every fixed n, assuming dimK ≤ 2n - 3. This is a substantial extension
of previous computational applications of topological degree and related concepts
in numerical and interval analysis. Via a reverse reduction, we prove that the
problem is undecidable when dim K > 2n - 2, where the threshold comes from
the stable range in homotopy theory. For the lucidity of our exposition, we focus
on the setting when f is simplexwise linear. Such functions can approximate general
continuous functions, and thus we get approximation schemes and undecidability
of the robust satisfiability in other possible settings.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Peter
foaf_name: Franek, Peter
foaf_surname: Franek
- foaf_Person:
foaf_givenName: Marek
foaf_name: Krcál, Marek
foaf_surname: Krcál
foaf_workInfoHomepage: http://www.librecat.org/personId=33E21118-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1145/2751524
bibo_issue: '4'
bibo_volume: 62
dct_date: 2015^xs_gYear
dct_language: eng
dct_publisher: ACM@
dct_title: Robust satisfiability of systems of equations@
...