{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:09Z","timestamp":1750306449632,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,9,11]],"date-time":"2015-09-11T00:00:00Z","timestamp":1441929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001824","name":"GA \u010cR","doi-asserted-by":"crossref","award":["P202\/12\/G061"],"award-info":[{"award-number":["P202\/12\/G061"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Center of Excellence -- Institute for Theoretical Computer Science, Prague"},{"name":"ERCCZ CORES","award":["LL1201"],"award-info":[{"award-number":["LL1201"]}]},{"name":"institutional support","award":["RVO:67985807"],"award-info":[{"award-number":["RVO:67985807"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,9,11]]},"abstract":"<jats:p>\n            We study the problem of\n            <jats:italic>robust satisfiability<\/jats:italic>\n            of systems of nonlinear equations, namely, whether for a given continuous function\n            <jats:italic>f<\/jats:italic>\n            :\n            <jats:italic>K<\/jats:italic>\n            \u2192 Rn on a finite simplicial complex\n            <jats:italic>K<\/jats:italic>\n            and \u03b1&gt;0, it holds that each function\n            <jats:italic>g<\/jats:italic>\n            :\n            <jats:italic>K<\/jats:italic>\n            \u2192 Rn such that \u2551\n            <jats:italic>g\u2212f<\/jats:italic>\n            \u2551\u221e \u2264\n            <jats:italic>\u03b1<\/jats:italic>\n            , has a root in\n            <jats:italic>K<\/jats:italic>\n            . 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            <jats:italic>n<\/jats:italic>\n            , assuming dim\n            <jats:italic>K<\/jats:italic>\n            \u2264 2\n            <jats:italic>n<\/jats:italic>\n            \u22123. This is a substantial extension of previous computational applications of\n            <jats:italic>topological degree<\/jats:italic>\n            and related concepts in numerical and interval analysis.\n          <\/jats:p>\n          <jats:p>\n            Via a reverse reduction, we prove that the problem is undecidable when dim\n            <jats:italic>K<\/jats:italic>\n            \u2265 2\n            <jats:italic>n<\/jats:italic>\n            \u22122, where the threshold comes from the\n            <jats:italic>stable range<\/jats:italic>\n            in homotopy theory.\n          <\/jats:p>\n          <jats:p>\n            For the lucidity of our exposition, we focus on the setting when\n            <jats:italic>f<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/2751524","type":"journal-article","created":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T12:09:15Z","timestamp":1442318955000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Robust Satisfiability of Systems of Equations"],"prefix":"10.1145","volume":"62","author":[{"given":"Peter","family":"Franek","sequence":"first","affiliation":[{"name":"Institute of Computer Science, ASCR Prague"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Kr\u010d\u00e1l","sequence":"additional","affiliation":[{"name":"IST Austria,Klosterneuburg"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,9,11]]},"reference":[{"volume-title":"Introduction to Homotopy Theory","author":"Arkowitz M.","key":"e_1_2_1_1_1","unstructured":"M. Arkowitz. 2011. Introduction to Homotopy Theory. Springer, New York. http:\/\/books.google.cz\/books?id=5nSCRSN51aoC."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/pamm.200510328"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"A. Ben-Tal L.E. Ghaoui and A. Nemirovski. 2009. Robust Optimization. Princeton University Press. http:\/\/books.google.cz\/books?id=DttjR7IpjUEC.","DOI":"10.1515\/9781400831050"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/2373695"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.2001.198.49"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9551-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/120899029"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-09-01249-X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2012.01.046"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2012.01.046"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.12.005"},{"volume-title":"Fixed Points and Topological Degree in Nonlinear Analysis","author":"Cronin J.","key":"e_1_2_1_13_1","unstructured":"J. Cronin. 1964. Fixed Points and Topological Degree in Nonlinear Analysis. American Mathematical Society. http:\/\/www.google.cz\/books?id=Zcyv3fHHd3wC"},{"volume-title":"A Course in Topological Combinatorics","author":"de Longueville M.","key":"e_1_2_1_14_1","unstructured":"M. de Longueville. 2012. A Course in Topological Combinatorics. Springer. http:\/\/books.google.cz\/books?id=L3KMSTHvigwC."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Jianwei Dian and R. B. Kearfott. 2003. Existence verification for singular and nonsmooth zeros of real nonlinear systems. Math. Comput. 72 242 757--766. 10.1090\/S0025-5718-02-01427-8","DOI":"10.1090\/S0025-5718-02-01427-8"},{"key":"e_1_2_1_16_1","volume-title":"Surveys on Discrete and Computational Geometry, Contemporary Mathematics","volume":"453","author":"Edelsbrunner H.","unstructured":"H. Edelsbrunner and J. Harer. 2008. Persistent homology---a survey. In Surveys on Discrete and Computational Geometry, Contemporary Mathematics, vol. 453, American Mathematical Society, Providence, RI, 257--282."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9090-8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971156"},{"key":"e_1_2_1_19_1","first-page":"B48c","article-title":"A user\u2019s guide to discrete Morse theory","volume":"48","author":"Forman Robin","year":"2002","unstructured":"Robin Forman. 2002. A user\u2019s guide to discrete Morse theory. S\u00e9m. Lothar. Combin 48, B48c.","journal-title":"S\u00e9m. Lothar. Combin"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2014-02877-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"P. Franek S. Ratschan and P. Zgliczynski. 2015. Quasi-decidability of a fragment of the analytic first-order theory of real numbers. Preprint arXiv:1309.6280.","DOI":"10.1007\/s10817-015-9351-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2005.07.030"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142903438148"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-004-0064-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4180-5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-05-07820-2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"F. Goudail and P. R\u00e9fr\u00e9gier. 2004. Statistical Image Processing Techniques for Noisy Images: An Application-Oriented Approach. Kluwer Academic\/Plenum Publishers. http:\/\/books.google.cz\/books?id=zkV45S0V3GUC.","DOI":"10.5555\/975068"},{"volume-title":"Cambridge University Press","author":"Hatcher A.","key":"e_1_2_1_28_1","unstructured":"A. Hatcher. 2001. Algebraic Topology. Cambridge University Press, Cambridge, UK. http:\/\/www.math.cornell.edu\/~hatcher\/AT\/ATpage.html."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/579525"},{"key":"e_1_2_1_30_1","unstructured":"S. T. Hu and V. Hu. 1959. Homotopy Theory. Elsevier Science. http:\/\/books.google.cz\/books?id=iVhMPU0X2G4C."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142901386057"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1515\/CRELLE.2006.075"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11784-007-0046-1"},{"volume-title":"Lectures on Algebraic Topology","author":"Matveev S. V.","key":"e_1_2_1_34_1","unstructured":"S. V. Matveev. 2006. Lectures on Algebraic Topology. European Mathematical Society. http:\/\/books.google.cz\/books?id=8vu6sCdyAykC."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1508122"},{"key":"e_1_2_1_36_1","unstructured":"R. E. Mosher and M. C. Tangora. 1968. Cohomology Operations and Applications in Homotopy Theory. Harper & Row Publishers New York. x+214 pages."},{"volume-title":"Interval Methods for Systems of Equations","author":"Neumaier A.","key":"e_1_2_1_37_1","unstructured":"A. Neumaier. 1990. Interval Methods for Systems of Equations. Cambridge Univ. Press, Cambridge, UK."},{"volume-title":"Elements of Homology Theory","author":"Prasolov V. V.","key":"e_1_2_1_38_1","unstructured":"V. V. Prasolov. 2007. Elements of Homology Theory. American Mathematical Society."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0717015"},{"volume-title":"An Introduction to Algebraic Topology","author":"Rotman J. J.","key":"e_1_2_1_40_1","unstructured":"J. J. Rotman. 1988. An Introduction to Algebraic Topology. Springer. http:\/\/books.google.at\/books?id=waq9mwUmcQgC."},{"key":"e_1_2_1_41_1","unstructured":"C. P. Rourke and B. J. Sanderson. 1982. Introduction to Piecewise-Linear Topology. Springer-Verlag. http:\/\/books.google.cz\/books?id=NkPvAAAAMAAJ."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/17634"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/PacificVis.2014.17"},{"key":"e_1_2_1_44_1","unstructured":"Andrew Paul Smith. 2012. Enclosure methods for systems of polynomial equations and inequalities. Dissertation thesis. http:\/\/kops.ub.uni-konstanz.de\/bitstream\/handle\/urn:nbn:de:bsz:352-208986\/Diss_Smith.pdf?sequence=1."},{"key":"e_1_2_1_45_1","unstructured":"E.H. Spanier. 1994. Algebraic Topology. Springer. http:\/\/books.google.cz\/books?id=h-wc3TnZMCcC."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(98)00055-3"},{"key":"e_1_2_1_47_1","unstructured":"L. Vok\u0159\u00ednek. 2014. Decidability of the extension problem for maps into odd-dimensional spheres. ArXiv e-prints."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321856"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2751524","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2751524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:07Z","timestamp":1750225387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2751524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,11]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,9,11]]}},"alternative-id":["10.1145\/2751524"],"URL":"https:\/\/doi.org\/10.1145\/2751524","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2015,9,11]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}