{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T02:03:13Z","timestamp":1760061793753},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s10208-019-09431-1","type":"journal-article","created":{"date-parts":[[2019,10,26]],"date-time":"2019-10-26T00:16:04Z","timestamp":1572048964000},"page":"753-781","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Tropical Combinatorial Nullstellensatz and Sparse Polynomials"],"prefix":"10.1007","volume":"20","author":[{"given":"Dima","family":"Grigoriev","sequence":"first","affiliation":[]},{"given":"Vladimir V.","family":"Podolskii","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,25]]},"reference":[{"key":"9431_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/495\/09689","volume":"495","author":"M Akian","year":"2009","unstructured":"M.\u00a0Akian, S.\u00a0Gaubert, and A.\u00a0Guterman. Linear independence over tropical semirings and beyond. Contemporary Mathematics, 495:1\u201333, 2009.","journal-title":"Contemporary Mathematics"},{"key":"9431_CR2","doi-asserted-by":"crossref","unstructured":"M.\u00a0Akian, S.\u00a0Gaubert, and A.\u00a0Guterman. Tropical polyhedra are equivalent to mean payoff games.International Journal of Algebra and Computation, 22(1), 2012.","DOI":"10.1142\/S0218196711006674"},{"issue":"1","key":"9431_CR3","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1137\/17M1142132","volume":"2","author":"X Allamigeon","year":"2018","unstructured":"X.\u00a0Allamigeon, P.\u00a0Benchimol, S.\u00a0Gaubert, and M.\u00a0Joswig. Log-barrier interior point methods are not strongly polynomial. SIAM Journal on Applied Algebra and Geometry, 2(1):140\u2013178, 2018.","journal-title":"SIAM Journal on Applied Algebra and Geometry"},{"issue":"1\u20132","key":"9431_CR4","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1017\/S0963548398003411","volume":"8","author":"N Alon","year":"1999","unstructured":"N.\u00a0Alon. Combinatorial Nullstellensatz. Comb. Probab. Comput., 8(1\u20132):7\u201329, Jan. 1999.","journal-title":"Comb. Probab. Comput."},{"key":"9431_CR5","doi-asserted-by":"crossref","unstructured":"S.\u00a0Basu, R.\u00a0Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, 2006.","DOI":"10.1007\/3-540-33099-2"},{"key":"9431_CR6","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ben-Or and P.\u00a0Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC\u201988, pages 301\u2013309, New York, NY, USA, 1988. ACM.","DOI":"10.1145\/62212.62241"},{"issue":"4","key":"9431_CR7","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1007\/s00454-016-9780-8","volume":"55","author":"F Bihan","year":"2016","unstructured":"F.\u00a0Bihan. Irrational mixed decomposition and sharp fewnomial bounds for tropical polynomial systems. Discrete & Computational Geometry, 55(4):907\u2013933, 2016.","journal-title":"Discrete & Computational Geometry"},{"key":"9431_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L Blum","year":"1998","unstructured":"L.\u00a0Blum, F.\u00a0Cucker, M.\u00a0Shub, and S.\u00a0Smale. Complexity and Real Computation. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1998."},{"key":"9431_CR9","unstructured":"P.\u00a0Brass, W.\u00a0O.\u00a0J. Moser, and J.\u00a0Pach. Research problems in discrete geometry. Springer, 2005."},{"issue":"5","key":"9431_CR10","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/S0097539793250330","volume":"24","author":"S Chari","year":"1995","unstructured":"S.\u00a0Chari, P.\u00a0Rohatgi, and A.\u00a0Srinivasan. Randomness-optimal unique element isolation with applications to perfect matching and related problems. SIAM Journal on Computing, 24(5):1036\u20131050, 1995.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"9431_CR11","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0166-218X(80)90025-6","volume":"2","author":"RA Cuninghame-Green","year":"1980","unstructured":"R.\u00a0A. Cuninghame-Green and P.\u00a0F.\u00a0J. Meijer. An algebra for piecewise-linear minimax problems. Discrete Applied Mathematics, 2(4):267\u2013294, 1980.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"9431_CR12","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1007\/s00454-016-9839-6","volume":"57","author":"A Davydow","year":"2017","unstructured":"A.\u00a0Davydow and D.\u00a0Grigoriev. Bounds on the number of connected components for tropical prevarieties. Discrete & Computational Geometry, 57(2):470\u2013493, 2017.","journal-title":"Discrete & Computational Geometry"},{"key":"9431_CR13","first-page":"213","volume":"52","author":"M Develin","year":"2005","unstructured":"M.\u00a0Develin, F.\u00a0Santos, and B.\u00a0Sturmfels. On the rank of a tropical matrix. Combinatorial and computational geometry, 52:213\u2013242, 2005.","journal-title":"Combinatorial and computational geometry"},{"issue":"1","key":"9431_CR14","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s00037-012-0053-5","volume":"22","author":"D Grigoriev","year":"2013","unstructured":"D.\u00a0Grigoriev. Complexity of solving tropical linear systems. Computational Complexity, 22(1):71\u201388, 2013.","journal-title":"Computational Complexity"},{"key":"9431_CR15","doi-asserted-by":"crossref","unstructured":"D.\u00a0Grigoriev and M.\u00a0Karpinski. The matching problem for bipartite graphs with polynomially bounded permanents is in NC (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27\u201329 October 1987, pages 166\u2013172, 1987.","DOI":"10.1109\/SFCS.1987.56"},{"issue":"1","key":"9431_CR16","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00037-013-0077-5","volume":"24","author":"D Grigoriev","year":"2015","unstructured":"D.\u00a0Grigoriev and V.\u00a0Podolskii. Complexity of tropical and min-plus linear prevarieties. Computational Complexity, 24(1):31\u201364, 2015.","journal-title":"Computational Complexity"},{"key":"9431_CR17","doi-asserted-by":"crossref","unstructured":"D.\u00a0Grigoriev and V.\u00a0V. Podolskii. Tropical combinatorial Nullstellensatz and fewnomials testing. In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11\u201313, 2017, Proceedings, pages 284\u2013297, 2017.","DOI":"10.1007\/978-3-662-55751-8_23"},{"issue":"3","key":"9431_CR18","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s00454-018-9966-3","volume":"59","author":"D Grigoriev","year":"2018","unstructured":"D.\u00a0Grigoriev and V.\u00a0V. Podolskii. Tropical effective primary and dual Nullstellens\u00e4tze. Discrete & Computational Geometry, 59(3):507\u2013552, 2018.","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"9431_CR19","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0196-8858(91)90005-4","volume":"12","author":"DY Grigoriev","year":"1991","unstructured":"D.\u00a0Y. Grigoriev, M.\u00a0Karpinski, and M.\u00a0F. Singer. The interpolation problem for k-sparse sums of eigenfunctions of operators. Advances in Applied Mathematics, 12(1):76 \u2013 81, 1991.","journal-title":"Advances in Applied Mathematics"},{"issue":"5","key":"9431_CR20","first-page":"887","volume":"2009","author":"RG Halburd","year":"2009","unstructured":"R.\u00a0G. Halburd and N.\u00a0J. Southall. Tropical Nevanlinna theory and ultradiscrete equations. International Mathematics Research Notices, 2009(5):887\u2013911, 2009.","journal-title":"International Mathematics Research Notices"},{"key":"9431_CR21","volume-title":"Inequalities","author":"G Hardy","year":"1988","unstructured":"G.\u00a0Hardy, J.\u00a0Littlewood, and G.\u00a0P\u00f3lya. Inequalities. Cambridge Mathematical Library. Cambridge University Press, 1988."},{"key":"9431_CR22","doi-asserted-by":"crossref","first-page":"1541","DOI":"10.1090\/S0025-5718-1995-1297471-4","volume":"64","author":"B Huber","year":"1995","unstructured":"B.\u00a0Huber and B.\u00a0Sturmfels. A polyhedral method for solving sparse polynomial systems. Mathematics of Computation, 64:1541\u20131555, 1995.","journal-title":"Mathematics of Computation"},{"key":"9431_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0346-0048-4","volume-title":"Tropical Algebraic Geometry","author":"I Itenberg","year":"2009","unstructured":"I.\u00a0Itenberg, G.\u00a0Mikhalkin, and E.\u00a0Shustin. Tropical Algebraic Geometry. Oberwolfach Seminars. Birkh\u00e4user, 2009."},{"issue":"11","key":"9431_CR24","doi-asserted-by":"crossref","first-page":"3912","DOI":"10.1080\/00927870902828793","volume":"37","author":"Z Izhakian","year":"2009","unstructured":"Z.\u00a0Izhakian and L.\u00a0Rowen. The tropical rank of a tropical matrix. Communications in Algebra, 37(11):3912\u20133927, 2009.","journal-title":"Communications in Algebra"},{"key":"9431_CR25","doi-asserted-by":"crossref","unstructured":"E.\u00a0Kaltofen and L.\u00a0Yagati. Improved sparse multivariate polynomial interpolation algorithms, pages 467\u2013474. Springer Berlin Heidelberg, Berlin, Heidelberg, 1989.","DOI":"10.1007\/3-540-51084-2_44"},{"key":"9431_CR26","doi-asserted-by":"crossref","unstructured":"A.\u00a0R. Klivans and D.\u00a0Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC \u201901, pages 216\u2013223, New York, NY, USA, 2001. ACM.","DOI":"10.1145\/380752.380801"},{"key":"9431_CR27","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.jsc.2014.09.036","volume":"68","author":"P Koiran","year":"2015","unstructured":"P.\u00a0Koiran, N.\u00a0Portier, and S.\u00a0Tavenas. A Wronskian approach to the real $$\\tau $$-conjecture. J. Symb. Comput., 68:195\u2013214, 2015.","journal-title":"J. Symb. Comput."},{"issue":"1","key":"9431_CR28","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s10208-014-9216-x","volume":"15","author":"P Koiran","year":"2015","unstructured":"P.\u00a0Koiran, N.\u00a0Portier, S.\u00a0Tavenas, and S.\u00a0Thomass\u00e9. A $$\\tau $$ -conjecture for Newton polygons. Foundations of Computational Mathematics, 15(1):185\u2013197, 2015.","journal-title":"Foundations of Computational Mathematics"},{"key":"9431_CR29","doi-asserted-by":"crossref","unstructured":"D.\u00a0Maclagan and B.\u00a0Sturmfels. Introduction to Tropical Geometry:. Graduate Studies in Mathematics. American Mathematical Society, 2015.","DOI":"10.1090\/gsm\/161"},{"key":"9431_CR30","series-title":"International Mathematical Series","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/0-306-48658-X_6","volume-title":"Different Faces of Geometry","author":"G Mikhalkin","year":"2004","unstructured":"G.\u00a0Mikhalkin. Amoebas of algebraic varieties and tropical geometry. In S.\u00a0Donaldson, Y.\u00a0Eliashberg, and M.\u00a0Gromov, editors, Different Faces of Geometry, volume\u00a03 of International Mathematical Series, pages 257\u2013300. Springer US, 2004."},{"key":"9431_CR31","unstructured":"G.\u00a0F. Mont\u00fafar, R.\u00a0Pascanu, K.\u00a0Cho, and Y.\u00a0Bengio. On the number of linear regions of deep neural networks. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 2924\u20132932, 2014."},{"issue":"1","key":"9431_CR32","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"K.\u00a0Mulmuley, U.\u00a0V. Vazirani, and V.\u00a0V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105\u2013113, 1987.","journal-title":"Combinatorica"},{"issue":"1","key":"9431_CR33","first-page":"297","volume":"43","author":"S Ovchinnikov","year":"2002","unstructured":"S.\u00a0Ovchinnikov. Max-min representation of piecewise linear functions. Beitr. Algebra Geom., 43(1):297\u2013302, 2002.","journal-title":"Beitr. Algebra Geom."},{"key":"9431_CR34","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1090\/conm\/377\/06998","volume":"377","author":"J Richter-Gebert","year":"2003","unstructured":"J.\u00a0Richter-Gebert, B.\u00a0Sturmfels, and T.\u00a0Theobald. First steps in tropical geometry. Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics, 377:289\u2013317, 2003.","journal-title":"Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics"},{"issue":"1","key":"9431_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0747-7171(08)80033-8","volume":"10","author":"J-J Risler","year":"1990","unstructured":"J.-J. Risler and F.\u00a0Ronga. Testing polynomials. Journal of Symbolic Computation, 10(1):1 \u2013 5, 1990.","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"9431_CR36","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"J.\u00a0T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701\u2013717, Oct. 1980.","journal-title":"J. ACM"},{"issue":"1","key":"9431_CR37","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1215\/S0012-7094-95-08105-8","volume":"81","author":"M Shub","year":"1995","unstructured":"M.\u00a0Shub and S.\u00a0Smale. On the intractability of Hilbert\u2019s Nullstellensatz and an algebraic version of $${NP}\\ne {P}$$? Duke Math. J., 81(1):47\u201354, 1995.","journal-title":"Duke Math. J."},{"issue":"12","key":"9431_CR38","doi-asserted-by":"crossref","first-page":"3815","DOI":"10.1090\/S0002-9939-07-09005-3","volume":"135","author":"E Shustin","year":"2007","unstructured":"E.\u00a0Shustin and Z.\u00a0Izhakian. A tropical Nullstellensatz. Proceedings of the American Mathematical Society, 135(12):3815\u20133821, 2007.","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"2","key":"9431_CR39","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF03025291","volume":"20","author":"S Smale","year":"1998","unstructured":"S.\u00a0Smale. Mathematical problems for the next century. The Mathematical Intelligencer, 20(2):7\u201315, Mar 1998.","journal-title":"The Mathematical Intelligencer"},{"issue":"1","key":"9431_CR40","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1137\/09075024X","volume":"24","author":"R Steffens","year":"2010","unstructured":"R.\u00a0Steffens and T.\u00a0Theobald. Combinatorics and genus of tropical intersections and Ehrhart theory. SIAM Journal on Discrete Mathematics, 24(1):17\u201332, 2010.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9431_CR41","doi-asserted-by":"crossref","unstructured":"B.\u00a0Sturmfels. Solving Systems of Polynomial Equations, volume\u00a097 of CBMS Regional Conference in Math. American Mathematical Society, 2002.","DOI":"10.1090\/cbms\/097"},{"key":"9431_CR42","unstructured":"N.\u00a0Ta-Shma. A simple proof of the isolation lemma. Electronic Colloquium on Computational Complexity (ECCC), 22:80, 2015."},{"issue":"12","key":"9431_CR43","doi-asserted-by":"crossref","first-page":"1360","DOI":"10.1016\/j.jsc.2005.11.006","volume":"41","author":"T Theobald","year":"2006","unstructured":"T.\u00a0Theobald. On the frontiers of polynomial computations in tropical geometry. J. Symb. Comput., 41(12):1360\u20131375, 2006.","journal-title":"J. Symb. Comput."},{"issue":"2","key":"9431_CR44","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0166-218X(94)00120-3","volume":"64","author":"M Urabe","year":"1996","unstructured":"M.\u00a0Urabe. On a partition into convex polygons. Discrete Applied Mathematics, 64(2):179 \u2013 191, 1996.","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"9431_CR45","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0925-7721(99)00020-6","volume":"13","author":"M Urabe","year":"1999","unstructured":"M.\u00a0Urabe. Partitioning point sets in space into disjoint convex polytopes. Computational Geometry, 13(3):173 \u2013 178, 1999.","journal-title":"Computational Geometry"},{"issue":"1","key":"9431_CR46","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0012-365X(92)90665-3","volume":"108","author":"P Valtr","year":"1992","unstructured":"P.\u00a0Valtr. Sets in $${\\mathbb{R}}^{d}$$ with no large empty convex subsets. Discrete Mathematics, 108(1):115 \u2013 124, 1992.","journal-title":"Discrete Mathematics"},{"key":"9431_CR47","first-page":"39","volume":"3","author":"N Vorobyev","year":"1967","unstructured":"N.\u00a0Vorobyev. Extremal algebra of positive matrices. Elektron. Informationsverarbeitung und Kybernetik, 3:39\u201371, 1967.","journal-title":"Elektron. Informationsverarbeitung und Kybernetik"},{"key":"9431_CR48","doi-asserted-by":"crossref","unstructured":"R.\u00a0Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, EUROSAM \u201979, pages 216\u2013226, London, UK, 1979. Springer-Verlag.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09431-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-019-09431-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09431-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T23:08:49Z","timestamp":1603494529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-019-09431-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,25]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["9431"],"URL":"https:\/\/doi.org\/10.1007\/s10208-019-09431-1","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,25]]},"assertion":[{"value":"25 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}