{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:26:02Z","timestamp":1759335962360},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,23]],"date-time":"2014-10-23T00:00:00Z","timestamp":1414022400000},"content-version":"tdm","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":[[2015,2]]},"DOI":"10.1007\/s10208-014-9216-x","type":"journal-article","created":{"date-parts":[[2014,10,22]],"date-time":"2014-10-22T20:00:08Z","timestamp":1414008008000},"page":"185-197","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A $$\\tau $$ \u03c4 -Conjecture for Newton Polygons"],"prefix":"10.1007","volume":"15","author":[{"given":"Pascal","family":"Koiran","sequence":"first","affiliation":[]},{"given":"Natacha","family":"Portier","sequence":"additional","affiliation":[]},{"given":"S\u00e9bastien","family":"Tavenas","sequence":"additional","affiliation":[]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,10,23]]},"reference":[{"key":"9216_CR1","doi-asserted-by":"crossref","unstructured":"M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proc. 49th IEEE Symposium on Foundations of Computer Science, pages 67\u201375, 2008.","DOI":"10.1109\/FOCS.2008.32"},{"key":"9216_CR2","doi-asserted-by":"crossref","unstructured":"O. B\u00edlka, K. Buchin, R. Fulek, M. Kiyomi, Y. Okamoto, S.I. Tanigawa, and C.D. T\u00f3th. A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets. Electr. J. Comb., 17(1), 2010.","DOI":"10.37236\/484"},{"key":"9216_CR3","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic settings for the problem \u201c $$\\text{ P } \\ne \\text{ NP }?$$ P \u2260 NP ? \u201d. In J. Renegar, M. Shub, and S. Smale, editors, The Mathematics of Numerical Analysis, volume 32 of Lectures in Applied Mathematics, pages 125\u2013144. American Mathematical Society, 1996.","DOI":"10.1007\/978-1-4612-0701-6_7"},{"key":"9216_CR4","doi-asserted-by":"crossref","unstructured":"L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1\u201346, July 1989.","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"9216_CR5","doi-asserted-by":"crossref","unstructured":"A. Borodin and S. Cook. On the number additions to compute specific polynomials. SIAM Journal on Computing, 5(1):146\u2013157, 1976.","DOI":"10.1137\/0205013"},{"key":"9216_CR6","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser. Completeness and Reduction in Algebraic Complexity Theory. Number 7 in Algorithms and Computation in Mathematics. Springer, 2000.","DOI":"10.1007\/978-3-662-04179-6"},{"key":"9216_CR7","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser. On defining integers and proving arithmetic circuit lower bounds. Computational Complexity, 18:81\u2013103, 2009. Conference version in STACS 2007.","DOI":"10.1007\/s00037-009-0260-x"},{"key":"9216_CR8","doi-asserted-by":"crossref","unstructured":"X. Chen, N. Kayal, and A. Wigderson. Partial derivatives in arithmetic complexity and beyond. Foundations and Trends in Theoretical Computer Science, 6(1):1\u2013138, 2011.","DOI":"10.1561\/0400000043"},{"key":"9216_CR9","doi-asserted-by":"crossref","unstructured":"F. Eisenbrand, J. Pach, T. Rothvo\u00df, and N.B. Sopher. Convexly independent subsets of the Minkowski sum of planar point sets. Electr. J. Comb., 15(1), 2008.","DOI":"10.37236\/883"},{"key":"9216_CR10","doi-asserted-by":"crossref","unstructured":"I. Fischer. Sums of like powers of multivariate linear forms. Mathematics Magazine, 67(1):59\u201361, 1994.","DOI":"10.2307\/2690560"},{"key":"9216_CR11","doi-asserted-by":"crossref","unstructured":"S. Gao. Absolute irreducibility of polynomials via Newton polytopes. Journal of Algebra, 237(2):501\u2013520, 2001.","DOI":"10.1006\/jabr.2000.8586"},{"key":"9216_CR12","doi-asserted-by":"crossref","unstructured":"A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Arithmetic circuits: A chasm at depth three. Electronic Colloquium on Computational Complexity (ECCC), 20, 2013.","DOI":"10.1109\/FOCS.2013.68"},{"key":"9216_CR13","doi-asserted-by":"crossref","unstructured":"N. Halman, S. Onn, and U. Rothblum. The convex dimension of a graph. Discrete Applied Mathematics, 155:1373\u20131383, 2007.","DOI":"10.1016\/j.dam.2007.02.005"},{"key":"9216_CR14","doi-asserted-by":"crossref","unstructured":"P. Hrube\u0161. On the Real $$\\tau $$ \u03c4 -Conjecture and the Distribution of Complex Roots. Theory of Computing, 9(10):403\u2013411, 2013.","DOI":"10.4086\/toc.2013.v009a839"},{"key":"9216_CR15","unstructured":"N. Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19, 2012."},{"key":"9216_CR16","doi-asserted-by":"crossref","unstructured":"P. Koiran. Hilbert\u2019s Nullstellensatz is in the polynomial hierarchy. Journal of Complexity, 12(4):273\u2013286, 1996. Long version: DIMACS report 96\u201327.","DOI":"10.1006\/jcom.1996.0019"},{"key":"9216_CR17","unstructured":"P. Koiran. Shallow circuits with high-powered inputs. In Proc. Second Symposium on Innovations in Computer Science (ICS 2011), 2011. http:\/\/arxiv.org\/abs\/1004.4960"},{"key":"9216_CR18","unstructured":"P. Koiran. Arithmetic circuits: the chasm at depth four gets wider. Theoretical Computer Science, (448):56\u201365, 2012."},{"key":"9216_CR19","unstructured":"A.M. Ostrowski. \u00dcber die Bede\u00fct\u00fcng der Theorie der konvexen Polyeder f\u00fcr die formale Algebra. Jahresberichte Deutsche Math. Verein, 20:98\u201399, 1921."},{"key":"9216_CR20","doi-asserted-by":"crossref","unstructured":"A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3\u20134), 2010.","DOI":"10.1561\/0400000039"},{"key":"9216_CR21","doi-asserted-by":"crossref","unstructured":"M. Shub and S. Smale. On the intractability of Hilbert\u2019s Nullstellensatz and an algebraic version of \u201cP=NP\u201d. Duke Mathematical Journal, 81(1):47\u201354, 1995.","DOI":"10.1215\/S0012-7094-95-08105-8"},{"key":"9216_CR22","doi-asserted-by":"crossref","unstructured":"S. Smale. Mathematical problems for the next century. Mathematical Intelligencer, 20(2):7\u201315, 1998.","DOI":"10.1007\/BF03025291"},{"key":"9216_CR23","doi-asserted-by":"crossref","unstructured":"B. Sturmfels. Polynomial equations and convex polytopes. The American Mathematical Monthly, 105(10):907\u2013922, 1998.","DOI":"10.2307\/2589283"},{"key":"9216_CR24","doi-asserted-by":"crossref","unstructured":"K.J. Swanepoel and P. Valtr. Large convexly independent subsets of Minkowski sums. Electr. J. Comb., 17(1), 2010.","DOI":"10.37236\/418"},{"key":"9216_CR25","doi-asserted-by":"crossref","unstructured":"S. Tavenas. Improved bounds for reduction to depth 4 and depth 3. In Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2013.","DOI":"10.1007\/978-3-642-40313-2_71"},{"key":"9216_CR26","unstructured":"S. Tavenas. Bornes inf\u00e9rieures et sup\u00e9rieures pour les circuits arithm\u00e9tiques. PhD thesis, 2014."},{"key":"9216_CR27","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. Completeness classes in algebra. In Proc. 11th ACM Symposium on Theory of Computing, pages 249\u2013261, 1979.","DOI":"10.1145\/800135.804419"},{"key":"9216_CR28","unstructured":"L. G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic (an International Symposium held in honour of Ernst Specker), pages 365\u2013380. Monographie $$n^{o}$$ n o 30 de L\u2019Enseignement Math\u00e9matique, 1982."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9216-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-014-9216-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9216-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T02:19:51Z","timestamp":1598408391000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-014-9216-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,23]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9216"],"URL":"https:\/\/doi.org\/10.1007\/s10208-014-9216-x","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,23]]}}}