{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T12:49:48Z","timestamp":1745498988666,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480533"},{"type":"electronic","value":"9783662480540"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_27","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T11:57:29Z","timestamp":1439207849000},"page":"324-335","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials"],"prefix":"10.1007","author":[{"given":"Herv\u00e9","family":"Fournier","sequence":"first","affiliation":[]},{"given":"Nutan","family":"Limaye","sequence":"additional","affiliation":[]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Vinay, V.: Arithmetic circuits: a chasm at depth four. In: FOCS, pp. 67\u201375 (2008)","DOI":"10.1109\/FOCS.2008.32"},{"issue":"1\u20132","key":"27_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1017\/S0963548307008917","volume":"18","author":"N Alon","year":"2009","unstructured":"Alon, N.: Perturbed identity matrices have high rank: proof and applications. Comb. Probab. Comput. 18(1\u20132), 3\u201315 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W Baur","year":"1983","unstructured":"Baur, W., Strassen, V.: The complexity of partial derivatives. Theor. Comput. Sci. 22, 317\u2013330 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR4","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, pp. 128\u2013135 (2014)","DOI":"10.1145\/2591796.2591824"},{"key":"27_CR5","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) (2013)","DOI":"10.1109\/CCC.2013.16"},{"issue":"3","key":"27_CR6","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/s00037-011-0007-3","volume":"20","author":"P Hrubes","year":"2011","unstructured":"Hrubes, P., Yehudayoff, A.: Homogeneous formulas and symmetric polynomials. Comput. Complexity 20(3), 559\u2013578 (2011)","journal-title":"Comput. Complexity"},{"key":"27_CR7","first-page":"81","volume":"19","author":"N Kayal","year":"2012","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)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Kayal, N., Limaye, N., Saha, C., Srinivasan, S.: An exponential lower bound for homogeneous depth four arithmetic formulas. In: Foundations of Computer Science (FOCS) (2014)","DOI":"10.1145\/2591796.2591823"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Kayal, N., Saha, C., Saptharishi, R.: A super-polynomial lower bound for regular arithmetic formulas. In: STOC, pp. 146\u2013153 (2014)","DOI":"10.1145\/2591796.2591847"},{"issue":"4","key":"27_CR10","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0895480103434634","volume":"18","author":"P Keevash","year":"2005","unstructured":"Keevash, P., Sudakov, B.: Set systems with restricted cross-intersections and the minimum rank ofinclusion matrices. SIAM J. Discrete Math. 18(4), 713\u2013727 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"27_CR11","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. Theor. Comput. Sci. 448, 56\u201365 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR12","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: STOC, pp. 136\u2013145 (2014)","DOI":"10.1145\/2591796.2591827"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Kumar, M., Saraf, S.: On the power of homogeneous depth 4 arithmetic circuits. In: FOCS, pp. 364\u2013373 (2014)","DOI":"10.1109\/FOCS.2014.46"},{"key":"27_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)"},{"issue":"3","key":"27_CR15","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01294256","volume":"6","author":"N Nisan","year":"1997","unstructured":"Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. Comput. Complex. 6(3), 217\u2013234 (1997)","journal-title":"Comput. Complex."},{"issue":"1","key":"27_CR16","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2006.v002a006","volume":"2","author":"R Raz","year":"2006","unstructured":"Raz, R.: Separation of multilinear circuit and formula size. Theor. Comput. 2(1), 121\u2013135 (2006)","journal-title":"Theor. Comput."},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Raz, R.: Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2) (2009)","DOI":"10.1145\/1502793.1502797"},{"issue":"4","key":"27_CR18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A Razborov","year":"1987","unstructured":"Razborov, A.: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes Acad. Sci. USSR 41(4), 333\u2013338 (1987)","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"27_CR19","unstructured":"Saptharishi, R.: Unified Approaches to Polynomial Identity Testing and Lower Bounds. Ph.D thesis, Chennai Mathematical Institute (2013)"},{"issue":"4","key":"27_CR20","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1016\/S0022-0000(02)00021-1","volume":"65","author":"A Shpilka","year":"2002","unstructured":"Shpilka, A.: Affine projections of symmetric polynomials. J. Comput. Syst. Sci. 65(4), 639\u2013659 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"27_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00001609","volume":"10","author":"A Shpilka","year":"2001","unstructured":"Shpilka, A., Wigderson, A.: Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complex. 10(1), 1\u201327 (2001)","journal-title":"Comput. Complex."},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Tavenas, S.: Improved bounds for reduction to depth 4 and 3. In: Mathematical Foundations of Computer Science (MFCS) (2013)","DOI":"10.1007\/978-3-642-40313-2_71"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: 11th ACM Symposium on Theory of Computing (STOC), pp. 249\u2013261. New York, NY, USA (1979)","DOI":"10.1145\/800135.804419"},{"issue":"4","key":"27_CR24","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 J. Comput. 12(4), 641\u2013644 (1983)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"27_CR25","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1016\/S0195-6698(13)80046-7","volume":"11","author":"RM Wilson","year":"1990","unstructured":"Wilson, R.M.: A diagonal form for the incidence matrices of $$t$$-subsets vs. $$k$$-subsets. Eur. J. Comb. 11(6), 609\u2013615 (1990)","journal-title":"Eur. J. Comb."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T14:19:09Z","timestamp":1675865949000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_27","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":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}