{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T07:52:07Z","timestamp":1771573927023,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,9,7]],"date-time":"2021-09-07T00:00:00Z","timestamp":1630972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,7]],"date-time":"2021-09-07T00:00:00Z","timestamp":1630972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100013296","name":"Max Planck Institute for Mathematics in the Sciences","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100013296","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We initiate a study of the Euclidean distance degree in the context of sparse polynomials. Specifically, we consider a hypersurface <jats:inline-formula><jats:alternatives><jats:tex-math>$$f=0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> defined by a polynomial\u00a0<jats:italic>f<\/jats:italic> that is general given its support, such that the support contains the origin. We show that the Euclidean distance degree of <jats:inline-formula><jats:alternatives><jats:tex-math>$$f=0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> equals the mixed volume of the Newton polytopes of the associated Lagrange multiplier equations. We discuss the implication of our result for computational complexity and give a formula for the Euclidean distance degree when the Newton polytope is a rectangular parallelepiped.<\/jats:p>","DOI":"10.1007\/s10208-021-09534-8","type":"journal-article","created":{"date-parts":[[2021,9,7]],"date-time":"2021-09-07T18:09:59Z","timestamp":1631038199000},"page":"1743-1765","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Euclidean Distance Degree and Mixed Volume"],"prefix":"10.1007","volume":"22","author":[{"given":"P.","family":"Breiding","sequence":"first","affiliation":[]},{"given":"F.","family":"Sottile","sequence":"additional","affiliation":[]},{"given":"J.","family":"Woodcock","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,7]]},"reference":[{"issue":"8","key":"9534_CR1","doi-asserted-by":"publisher","first-page":"2005","DOI":"10.2140\/ant.2018.12.2005","volume":"12","author":"P Aluffi","year":"2018","unstructured":"Aluffi, P., Harris, C.: The Euclidean distance degree of smooth complex projective varieties. Algebra Number Theory 12(8), 2005\u20132032 (2018)","journal-title":"Algebra Number Theory"},{"issue":"6","key":"9534_CR2","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1006\/jsco.2002.0563","volume":"34","author":"P Aubry","year":"2002","unstructured":"Aubry, P., Rouillier, F., Safey Din, M.: Real solving for positive dimensional systems. J. Symbolic Comput. 34(6), 543\u2013560 (2002)","journal-title":"J. Symbolic Comput."},{"issue":"6","key":"9534_CR3","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"Basu, S., Pollack, R., Roy, M.F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43(6), 1002\u20131045 (1996)","journal-title":"J. ACM"},{"issue":"3","key":"9534_CR4","first-page":"1","volume":"9","author":"DN Bernstein","year":"1975","unstructured":"Bernstein, D.N.: The number of roots of a system of equations. Funkcional. Anal. i Prilo\u017een. 9(3), 1\u20134 (1975)","journal-title":"Funkcional. Anal. i Prilo\u017een."},{"issue":"3(189)","key":"9534_CR5","first-page":"201","volume":"31","author":"DN Bernstein","year":"1976","unstructured":"Bernstein, D.N., Ku\u0161nirenko, A.G., Hovanski\u012d, A.G.: Newton polyhedra. Uspehi Mat. Nauk 31(189), 201\u2013202 (1976)","journal-title":"Newton polyhedra. Uspehi Mat. Nauk"},{"key":"9534_CR6","unstructured":"Breiding, P., Rose, K., Timme, S.: Certifying zeros of polynomial systems using interval arithmetic. arXiv:2011.05000 (2020)"},{"key":"9534_CR7","doi-asserted-by":"crossref","unstructured":"Breiding, P., Timme, S.: HomotopyContinuation.jl: A Package for Homotopy Continuation in Julia. In: International Congress on Mathematical Software, pp. 458\u2013465. Springer, Berlin (2018)","DOI":"10.1007\/978-3-319-96418-8_54"},{"key":"9534_CR8","doi-asserted-by":"publisher","DOI":"10.1063\/5.0018562","author":"N Do","year":"2020","unstructured":"Do, N., Kuchment, P., Sottile, F.: Generic properties of dispersion relations for discrete periodic operators. J. Math. Phys. (2020). DOI:https:\/\/doi.org\/10.1063\/5.0018562","journal-title":"J. Math. Phys."},{"issue":"1","key":"9534_CR9","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s10208-014-9240-x","volume":"16","author":"J Draisma","year":"2016","unstructured":"Draisma, J., Horobe\u0163, E., Ottaviani, G., Sturmfels, B., Thomas, R.R.: The euclidean distance degree of an algebraic variety. Foundations of Computational Mathematics 16(1), 99\u2013149 (2016)","journal-title":"Found. Comput. Math."},{"issue":"8","key":"9534_CR10","first-page":"1116","volume":"67","author":"L Escobar","year":"2020","unstructured":"Escobar, L., Kaveh, K.: Convex polytopes, algebraic geometry, and combinatorics. Notices of the AMS 67(8), 1116\u20131123 (2020)","journal-title":"Notices of the AMS"},{"issue":"2","key":"9534_CR11","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1112\/S0010437X18007868","volume":"155","author":"A Esterov","year":"2019","unstructured":"Esterov, A.: Galois theory for general systems of polynomial equations. Compos. Math. 155(2), 229\u2013245 (2019)","journal-title":"Compos. Math."},{"key":"9534_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4044-0","volume-title":"Combinatorial convexity and algebraic geometry, Graduate Texts in Mathematics","author":"G Ewald","year":"1996","unstructured":"Ewald, G.: Combinatorial convexity and algebraic geometry, Graduate Texts in Mathematics, vol. 168. Springer-Verlag, New York (1996)"},{"key":"9534_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2189-8","volume-title":"Algebraic Geometry: A first course, Graduate Texts in Mathematics","author":"J Harris","year":"1992","unstructured":"Harris, J.: Algebraic Geometry: A first course, Graduate Texts in Mathematics, vol. 133. Springer-Verlag, New York (1992)"},{"issue":"1","key":"9534_CR14","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10440-012-9782-3","volume":"125","author":"JD Hauenstein","year":"2013","unstructured":"Hauenstein, J.D.: Numerically computing real points on algebraic sets. Acta Applicandae Mathematicae 125(1), 105\u2013119 (2013)","journal-title":"Acta Appl. Math."},{"key":"9534_CR15","doi-asserted-by":"publisher","DOI":"10.1145\/2331130.2331136","author":"JD Hauenstein","year":"2012","unstructured":"Hauenstein, J.D., Sottile, F.: Algorithm 921: alphaCertified: Certifying Solutions to Polynomial Systems. ACM Trans. Math. Softw. (2012). https:\/\/doi.org\/10.1145\/2331130.2331136.","journal-title":"ACM Trans. Math. Softw."},{"issue":"212","key":"9534_CR16","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1090\/S0025-5718-1995-1297471-4","volume":"64","author":"B Huber","year":"1995","unstructured":"Huber, B., Sturmfels, B.: A polyhedral method for solving sparse polynomial systems. Mathematics of Computation 64(212), 1541\u20131555 (1995)","journal-title":"Math. Comput."},{"issue":"1","key":"9534_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01389769","volume":"32","author":"AG Kouchnirenko","year":"1976","unstructured":"Kouchnirenko, A.G.: Poly\u00e8dres de Newton et nombres de Milnor. Invent. Math. 32(1), 1\u201331 (1976)","journal-title":"Invent. Math."},{"issue":"2","key":"9534_CR18","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/3371991.3371995","volume":"53","author":"K Lee","year":"2019","unstructured":"Lee, K.: Certifying approximate solutions to polynomial systems on Macaulay2. ACM Communications in Computer Algebra 53(2), 45\u201348 (2019)","journal-title":"ACM Commun. Comput. Algebra"},{"issue":"2","key":"9534_CR19","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s00607-008-0015-6","volume":"83","author":"TL Lee","year":"2008","unstructured":"Lee, T.L., Li, T.Y., Tsai, C.H.: Hom4ps-20: a software package for solving polynomial systems by the polyhedral homotopy continuation method. Computing 83(2), 109 (2008). https:\/\/doi.org\/10.1007\/s00607-008-0015-6.","journal-title":"Computing"},{"issue":"5","key":"9534_CR20","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1007\/s10208-016-9320-1","volume":"17","author":"G Malajovich","year":"2017","unstructured":"Malajovich, G.: Computing mixed volume and all mixed cells in quermassintegral time. J. Foundations of Computational Mathematics 17(5), 1293\u20131334 (2017)","journal-title":"J. Found. Comput. Math."},{"issue":"1","key":"9534_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10208-018-9375-2","volume":"19","author":"G Malajovich","year":"2019","unstructured":"Malajovich, G.: Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric. J. Foundations of Computational Mathematics 19(1), 1\u201353 (2019)","journal-title":"J. Found. Comput. Math."},{"key":"9534_CR22","unstructured":"Malajovich, G.: Complexity of sparse polynomial solving 2: Renormalization (2020)"},{"issue":"1","key":"9534_CR23","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/18M1233406","volume":"4","author":"LG Maxim","year":"2020","unstructured":"Maxim, L.G., Rodriguez, J.I., Wang, B.: Euclidean distance degree of the multiview variety. SIAM J. Appl. Algebra Geom. 4(1), 28\u201348 (2020)","journal-title":"SIAM J. Appl. Algebra Geom."},{"issue":"4","key":"9534_CR24","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1006\/jcom.2000.0563","volume":"16","author":"F Rouillier","year":"2000","unstructured":"Rouillier, F., Roy, M.F., El Din, M.S.: Finding at least one point in each connected component of a real algebraic set defined by a single equation. J. Complexity 16(4), 716\u2013750 (2000)","journal-title":"J. Complexity"},{"key":"9534_CR25","doi-asserted-by":"crossref","unstructured":"Rump, S.: INTLAB - INTerval LABoratory. In: Developments in Reliable Computing, pp. 77\u2013104. Kluwer Academic Publishers (1999)","DOI":"10.1007\/978-94-017-1247-7_7"},{"issue":"2","key":"9534_CR26","doi-asserted-by":"publisher","first-page":"365","DOI":"10.2307\/1969640","volume":"60","author":"A Seidenberg","year":"1954","unstructured":"Seidenberg, A.: A new decision method for elementary algebra. Annals of Mathematics 60(2), 365\u2013374 (1954)","journal-title":"Ann. Math."},{"key":"9534_CR27","doi-asserted-by":"publisher","DOI":"10.1142\/5763","author":"A Sommese","year":"2005","unstructured":"Sommese, A., Wampler, C.: The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific (2005). https:\/\/doi.org\/10.1142\/5763","journal-title":"World Sci."},{"issue":"2","key":"9534_CR28","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.comgeo.2009.04.004","volume":"43","author":"R Steffens","year":"2010","unstructured":"Steffens, R., Theobald, T.: Mixed volume techniques for embeddings of Laman graphs. Comput. Geom. 43(2), 84\u201393 (2010)","journal-title":"Comput. Geom."},{"key":"9534_CR29","doi-asserted-by":"crossref","unstructured":"Verschelde, J.: Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25(2), 251\u2013276 (1999). http:\/\/dblp.uni-trier.de\/db\/journals\/toms\/toms25.html#Verschelde99","DOI":"10.1145\/317275.317286"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09534-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09534-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09534-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,14]],"date-time":"2022-11-14T23:59:51Z","timestamp":1668470391000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09534-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,7]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["9534"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09534-8","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,7]]},"assertion":[{"value":"22 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}