{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T04:12:52Z","timestamp":1771474372090,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"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":["comput. complex."],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00037-023-00236-x","type":"journal-article","created":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T08:02:21Z","timestamp":1683964941000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Schur Polynomials Do Not Have Small Formulas If the Determinant does not"],"prefix":"10.1007","volume":"32","author":[{"given":"Prasad","family":"Chaugule","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mrinal","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nutan","family":"Limaye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chandra Kanta","family":"Mohapatra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"She","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,13]]},"reference":[{"key":"236_CR1","doi-asserted-by":"crossref","unstructured":"Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay & S. Raja (2019). Randomized Polynomial-Time Identity Testing for Non commutative Circuits. Theory of Computing 15(7), 1\u201336.","DOI":"10.4086\/toc.2019.v015a007"},{"key":"236_CR2","unstructured":"Markus Bl\u00e4ser & Gorav Jindal (2018). On the Complexity of Symmetric Polynomials. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), Avrim Blum, editor, volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), 47:1\u201347:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. ISBN 978-3-95977-095-8. ISSN 1868-8969 URL http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/10140."},{"key":"236_CR3","unstructured":"Peter B\u00fcrgisser (2000). Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and computation in mathematics.Springer. ISBN 978-3-540-66752-0."},{"key":"236_CR4","doi-asserted-by":"crossref","unstructured":"Cy Chan, Vesselin Drensky, Alan Edelman, Raymond Kan & Plamen Koev (2019). On computing Schur functions and series thereof. Journal of Algebraic Combinatorics 50(2), 127\u2013141. ISSN 1572-9192.URL https:\/\/doi.org\/10.1007\/s10801-018-0846-y.","DOI":"10.1007\/s10801-018-0846-y"},{"key":"236_CR5","unstructured":"Xi Chen, Neeraj Kayal & Avi Wigderson (2011). Partial Derivatives in Arithmetic Complexity. Foundations and Trends in Theoretical Computer Science ."},{"key":"236_CR6","unstructured":"Chi-Ning Chou, Mrinal Kumar & Noam Solomon (2018). Some Closure Results for Polynomial Factorization and Applications. CoRR abs\/1803.05933. URL http:\/\/arxiv.org\/abs\/1803.05933."},{"key":"236_CR7","unstructured":"Chi-Ning Chou, Mrinal Kumar & Noam Solomon (2019). Closure of VP under taking factors: a short and simple proof. CoRR abs\/1903.02366. URL http:\/\/arxiv.org\/abs\/1903.02366."},{"key":"236_CR8","doi-asserted-by":"crossref","unstructured":"James Demmel & Plamen Koev (2006). Accurate and Efficient Evaluation of Schur and Jack Functions. Mathematics of Computation 75(253), 223\u2013239. ISSN 00255718, 10886842. URL http:\/\/www.jstor.org\/stable\/4100151.","DOI":"10.1090\/S0025-5718-05-01780-1"},{"key":"236_CR9","doi-asserted-by":"crossref","unstructured":"Pranjal Dutta, Nitin Saxena & Amit Sinhababu (2018). Discovering the roots: Uniform closure results for algebraic classes under factoring. In STOC, 1152\u20131165.","DOI":"10.1145\/3188745.3188760"},{"key":"236_CR10","doi-asserted-by":"crossref","unstructured":"Zeev Dvir, Amir Shpilka & Amir Yehudayoff (2010). Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. SIAM J. Comput. 39(4), 1279\u20131293. Preliminary version in","DOI":"10.1137\/080735850"},{"key":"236_CR11","unstructured":"Philippe Flajolet & Robert Sedgewick (2014). Analytic Combinatorics.Cambridge University Press."},{"key":"236_CR12","doi-asserted-by":"crossref","unstructured":"Sergey Fomin, Dima Grigoriev & Gleb Koshevoy (2016). Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees. Found. Comput. Math. 16(1), 1\u201331. ISSN 1615-3375. URL http:\/\/dx.doi.org\/10.1007\/s10208-014-9231-y.","DOI":"10.1007\/s10208-014-9231-y"},{"key":"236_CR13","doi-asserted-by":"crossref","unstructured":"Sergey Fomin, Dima Grigoriev, Dorian Nogneng & \u00c9ric Schost (2018). On Semiring Complexity of Schur Polynomials. Comput. Complex. 27(4), 595\u2013616. ISSN 1016-3328. URL https:\/\/doi.org\/10.1007\/s00037-018-0169-3.","DOI":"10.1007\/s00037-018-0169-3"},{"key":"236_CR14","doi-asserted-by":"crossref","unstructured":"Herv\u00e9 Fournier, Nutan Limaye, Meena Mahajan & Srikanth Srinivasan (2017). The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. Theory of Computing 13(1), 1\u201334.URL  https:\/\/doi.org\/10.4086\/toc.2017.v013a009.","DOI":"10.4086\/toc.2017.v013a009"},{"key":"236_CR15","doi-asserted-by":"crossref","unstructured":"Vesselin Gasharov (1996). Incomparability graphs of (3+ 1)-free posets are s-positive. Discrete Mathematics 157(1-3), 193\u2013197.","DOI":"10.1016\/S0012-365X(96)83014-7"},{"key":"236_CR16","doi-asserted-by":"crossref","unstructured":"Dima Grigoriev & Gleb Koshevoy (2016). Complexity of tropical Schur polynomials. Journal of Symbolic Computation 74, 46 \u2013 54. ISSN 0747-7171. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0747717115000516.","DOI":"10.1016\/j.jsc.2015.05.005"},{"key":"236_CR17","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2016). Arithmetic Circuits: A Chasm at Depth 3. SIAMJ. Comput. 45(3), 1064\u20131079.URL  http:\/\/dx.doi.org\/10.1137\/140957123.","DOI":"10.1137\/140957123"},{"key":"236_CR18","doi-asserted-by":"crossref","unstructured":"Sean Hallgren, Alexander Russell & Amnon Ta-Shma (2000).Normal subgroup reconstruction and quantum computation using group representations. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, 627\u2013635. ACM. URL http:\/\/www.jstor.org\/stable\/1989528..","DOI":"10.1145\/335305.335392"},{"key":"236_CR19","doi-asserted-by":"crossref","unstructured":"E. R. Heineman (1929). Generalized Vandermonde Determinants. Transactions of the American Mathematical Society 31(3), 464\u2013476. ISSN 00029947. URL http:\/\/www.jstor.org\/stable\/1989528.","DOI":"10.1090\/S0002-9947-1929-1501494-2"},{"key":"236_CR20","doi-asserted-by":"crossref","unstructured":"Pavel Hrubes & Amir Yehudayoff (2011). Homogeneous Formulas and Symmetric Polynomials. Computational Complexity 20(3), 559\u2013578. URL https:\/\/doi.org\/10.1007\/s00037-011-0007-3.","DOI":"10.1007\/s00037-011-0007-3"},{"key":"236_CR21","doi-asserted-by":"crossref","unstructured":"Christian Ikenmeyer & Stefan Mengel (2018). On the relative power of reduction notions in arithmetic circuit complexity. Inf. Process. Lett. 130, 7\u201310. URL https:\/\/doi.org\/10.1016\/j.ipl.2017.09.009.","DOI":"10.1016\/j.ipl.2017.09.009"},{"key":"236_CR22","doi-asserted-by":"crossref","unstructured":"Christian Ikenmeyer & Greta Panova (2017). Rectangular Kronecker coefficients and plethysms in geometric complexity theory. Advances in Mathematics 319, 40\u201366.","DOI":"10.1016\/j.aim.2017.08.024"},{"key":"236_CR23","doi-asserted-by":"crossref","unstructured":"Valentine Kabanets & Russell Impagliazzo (2004). Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.Computational Complexity 13(1-2), 1\u201346.","DOI":"10.1007\/s00037-004-0182-6"},{"key":"236_CR24","unstructured":"Erich Kaltofen (1989). Factorization of Polynomials Given by Straight-Line Programs. In Randomness and Computation, 375\u2013412. JAI Press."},{"key":"236_CR25","doi-asserted-by":"crossref","unstructured":"Plamen. Koev (2007). Accurate Computations with Totally Nonnegative Matrices. SIAM Journal on Matrix Analysis and Applications 29(3), 731\u2013751. URL https:\/\/doi.org\/10.1137\/04061903X.","DOI":"10.1137\/04061903X"},{"key":"236_CR26","doi-asserted-by":"crossref","unstructured":"J. M. Landsberg & Zach Teitler (2010). On the Ranks and Border Ranks of Symmetric Tensors. Foundations of Computational Mathematics 10(3), 339\u2013366. ISSN 1615-3383. URL https:\/\/doi.org\/10.1007\/s10208-009-9055-3.","DOI":"10.1007\/s10208-009-9055-3"},{"key":"236_CR27","unstructured":"Veerle Ledoux & Simon JA Malham (2010). Introductory Schubert calculus."},{"key":"236_CR28","unstructured":"Dick Lipton & Ken Regan (2009). Arithmetic Complexity and Symmetry. URL https:\/\/rjlipton.wordpress.com\/2009\/07\/10\/arithmetic-complexity-and-symmetry\/."},{"key":"236_CR29","unstructured":"Ian G. Macdonald (1979). Symmetric functions and Hall polynomials. Oxford University Press."},{"key":"236_CR30","doi-asserted-by":"crossref","unstructured":"Hariharan Narayanan (2006). On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients. Journal of Algebraic Combinatorics 24(3), 347\u2013354.","DOI":"10.1007\/s10801-006-0008-5"},{"key":"236_CR31","doi-asserted-by":"crossref","unstructured":"Noam Nisan & Avi Wigderson (1997). Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity 6(3), 217\u2013 234. Available on citeseer:10.1.1.90.2644.","DOI":"10.1007\/BF01294256"},{"key":"236_CR32","doi-asserted-by":"crossref","unstructured":"Ryan O\u2019Donnell & John Wright (2015). Quantum Spectrum Testing.","DOI":"10.1145\/2746539.2746582"},{"key":"236_CR33","unstructured":"Luke Oeding (2016). Border Ranks of Monomials, Preprint arXiv:1608.02530."},{"key":"236_CR34","doi-asserted-by":"crossref","unstructured":"Bruce Sagan (2001). The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Springer.","DOI":"10.1007\/978-1-4757-6804-6_3"},{"key":"236_CR35","doi-asserted-by":"crossref","unstructured":"Nitin Saxena (2008). Diagonal circuit identity testing and lower bounds. In Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I 35, 60\u201371. Springer.","DOI":"10.1007\/978-3-540-70575-8_6"},{"key":"236_CR36","unstructured":"Amir Shpilka (2001). Affine Projections of Symmetric Polynomials. In In Proc. 16th Annual IEEE Conference on Computational Complexity, 160\u2013171."},{"key":"236_CR37","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Avi Wigderson (2001). Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10(1), 1\u201327.","DOI":"10.1007\/PL00001609"},{"key":"236_CR38","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5, 207\u2013388. ISSN 1551-305X.","DOI":"10.1561\/0400000039"},{"key":"236_CR39","unstructured":"Amit Sinhababu & Thomas Thierauf (2020). Factorization of Polynomials Given By Arithmetic Branching Programs. In 35th Computational Complexity Conference (CCC 2020), Shubhangi Saraf, editor, volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), 33:1\u201333:19. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00a8ur Informatik, Dagstuhl, Germany. ISBN 978-3-95977-156-6. ISSN 1868-8969. URL https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/12585."},{"key":"236_CR40","doi-asserted-by":"crossref","unstructured":"Richard P Stanley (1984). On the number of reduced decompositions of elements of Coxeter groups. European Journal of Combinatorics 5(4), 359\u2013372.","DOI":"10.1016\/S0195-6698(84)80039-6"},{"key":"236_CR41","doi-asserted-by":"crossref","unstructured":"Richard P Stanley (1995). A symmetric function generalization of the chromatic polynomial of a graph. Advances in Mathematics 111(1),166\u2013194.","DOI":"10.1006\/aima.1995.1020"},{"key":"236_CR42","doi-asserted-by":"crossref","unstructured":"Richard P Stanley (1999). Enumerative combinatorics. Vol. 2, volume 62 of. Cambridge Studies in Advanced Mathematics .","DOI":"10.1017\/CBO9780511609589"},{"key":"236_CR43","doi-asserted-by":"crossref","unstructured":"Richard P Stanley & John R Stembridge (1993). On immanants of Jacobi-Trudi matrices and permutations with restricted position. Journal of Combinatorial Theory, Series A 62(2), 261\u2013279.","DOI":"10.1016\/0097-3165(93)90048-D"},{"key":"236_CR44","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant, Sven Skyum, S. Berkowitz & Charles Rackoff (1983). Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput. 12(4), 641\u2013644.","DOI":"10.1137\/0212043"},{"key":"236_CR45","unstructured":"Herbert S. Wilf (2006). Generatingfunctionology. A. K. Peters, Ltd., 3rd edition. ISBN 1-56881-279-5 (hardcover), x + 245 ."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00236-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00236-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00236-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T17:04:50Z","timestamp":1687885490000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00236-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,13]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["236"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00236-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,13]]},"assertion":[{"value":"18 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}