{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T20:46:52Z","timestamp":1743022012042,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_66","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"810-821","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Lower Bounds for Sums of Powers of Low Degree Univariates"],"prefix":"10.1007","author":[{"given":"Neeraj","family":"Kayal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Koiran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timoth\u00e9e","family":"Pecatte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chandan","family":"Saha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"66_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Vinay, V.: Arithmetic circuits: a chasm at depth four. In: Foundations of Computer Science FOCS, pp. 67\u201375 (2008)","DOI":"10.1109\/FOCS.2008.32"},{"issue":"1\u20132","key":"66_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(97)00227-2","volume":"209","author":"E Allender","year":"1998","unstructured":"Allender, E., Jiao, J., Mahajan, M., Vinay, V.: Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Theor. Comput. Sci. 209(1\u20132), 47\u201386 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"66_CR3","unstructured":"Blekherman, G., Teitler, Z.: On maximum, typical and generic ranks. Mathematische Annalen, pp. 1\u201311 (2014)"},{"key":"66_CR4","doi-asserted-by":"crossref","unstructured":"Bocher, M.: The theory of linear dependence. Annals of Mathematics 2(1\/4), 81\u201396 (1900\u20131901)","DOI":"10.2307\/2007186"},{"key":"66_CR5","doi-asserted-by":"crossref","unstructured":"Fournier, H., Limaye, N., Malod, G., Srinivasan, S.: Lower bounds for depth 4 formulas computing iterated matrix multiplication. In: Symposium on Theory of Computing, STOC 2014, pp. 128\u2013135 (2014)","DOI":"10.1145\/2591796.2591824"},{"issue":"15","key":"66_CR6","doi-asserted-by":"publisher","first-page":"5600","DOI":"10.1073\/pnas.1120984109","volume":"109","author":"R Fr\u00f6berg","year":"2012","unstructured":"Fr\u00f6berg, R., Ottaviani, G., Shapiro, B.: On the Waring problem for polynomial rings. Proceedings of the National Academy of Sciences 109(15), 5600\u20135602 (2012)","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"66_CR7","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Approaching the chasm at depth four. In: Conference on Computational Complexity (CCC), pp. 65\u201373 (2013)","DOI":"10.1109\/CCC.2013.16"},{"key":"66_CR8","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Arithmetic circuits: a chasm at depth three. In: Foundations of Computer Science (FOCS), pp. 578\u2013587 (2013)","DOI":"10.1109\/FOCS.2013.68"},{"key":"66_CR9","unstructured":"Kayal, N.: An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC) 19, 81 (2012)"},{"key":"66_CR10","doi-asserted-by":"crossref","unstructured":"Kayal, N., Limaye, N., Saha, C., Srinivasan, S.: An exponential lower bound for homogeneous depth four arithmetic formulas. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 61\u201370 (2014)","DOI":"10.1109\/FOCS.2014.15"},{"key":"66_CR11","unstructured":"Kayal, N., Saha, C.: Lower bounds for depth three arithmetic circuits with small bottom fanin. Electronic Colloquium on Computational Complexity (ECCC) 21, 89 (2014)"},{"key":"66_CR12","doi-asserted-by":"crossref","unstructured":"Kayal, N., Saha, C., Saptharishi, R.: A super-polynomial lower bound for regular arithmetic formulas. In: Symposium on Theory of Computing, STOC 2014, pp. 146\u2013153 (2014)","DOI":"10.1145\/2591796.2591847"},{"key":"66_CR13","unstructured":"Kleppe, J.: Representing a Homogenous Polynomial as a Sum of Powers of Linear Forms. Thesis for the degree of Candidatus Scientiarum (University of Oslo) (1999). http:\/\/folk.uio.no\/johannkl\/kleppe-master.pdf"},{"key":"66_CR14","unstructured":"Koiran, P.: Shallow circuits with high-powered inputs. In: Proceedings of the Innovations in Computer Science - ICS 2010, pp. 309\u2013320. Tsinghua University, Beijing, 7\u20139 January 2011"},{"key":"66_CR15","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","volume":"448","author":"P Koiran","year":"2012","unstructured":"Koiran, P.: Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science 448, 56\u201365 (2012)","journal-title":"Theoretical Computer Science"},{"key":"66_CR16","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.jsc.2014.09.036","volume":"68","author":"P Koiran","year":"2015","unstructured":"Koiran, P., Portier, N., Tavenas, S.: A Wronskian approach to the real $$\\tau $$-conjecture. J. Symb. Comput. 68, 195\u2013214 (2015)","journal-title":"J. Symb. Comput."},{"key":"66_CR17","doi-asserted-by":"crossref","unstructured":"Kumar, M., Saraf, S.: The limits of depth reduction for arithmetic formulas: it\u2019s all about the top fan-in. In: Symposium on Theory of Computing, STOC, pp. 136\u2013145 (2014)","DOI":"10.1145\/2591796.2591827"},{"key":"66_CR18","doi-asserted-by":"crossref","unstructured":"Kumar, M., Saraf, S.: On the power of homogeneous depth 4 arithmetic circuits. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 364\u2013373 (2014)","DOI":"10.1109\/FOCS.2014.46"},{"key":"66_CR19","unstructured":"Pecatte, T.: Lower bounds for univariate polynomials: a Wronskian approach. M2 Internship Report (Ecole Normale Sup\u00e9rieure de Lyon) (2014). http:\/\/perso.ens-lyon.fr\/pascal.koiran\/timothee_pecatte_master2report.pdf"},{"key":"66_CR20","unstructured":"Polya, G., Szego, G.: Problems and Theorems in Analysis, vol. II. Springer (1976)"},{"key":"66_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1007\/978-3-642-40313-2_71","volume-title":"Mathematical Foundations of Computer Science 2013","author":"S Tavenas","year":"2013","unstructured":"Tavenas, S.: Improved bounds for reduction to depth 4 and depth 3. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 813\u2013824. Springer, Heidelberg (2013)"},{"key":"66_CR22","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Symposium on Theory of Computing STOC, pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"issue":"4","key":"66_CR23","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"LG Valiant","year":"1983","unstructured":"Valiant, L.G., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM Journal on Computing 12(4), 641\u2013644 (1983)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"66_CR24","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/1385-7258(75)90050-5","volume":"78","author":"M Voorhoeve","year":"1975","unstructured":"Voorhoeve, M., Van Der Pooerten, A.J.: Wronskian determinants and the zeros of certain functions. Indagationes Mathematicae 78(5), 417\u2013424 (1975)","journal-title":"Indagationes Mathematicae"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:44:41Z","timestamp":1676018681000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}