{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T14:00:00Z","timestamp":1775484000534,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,7,12]],"date-time":"2016-07-12T00:00:00Z","timestamp":1468281600000},"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":["comput. complex."],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00037-016-0142-y","type":"journal-article","created":{"date-parts":[[2016,7,12]],"date-time":"2016-07-12T08:55:07Z","timestamp":1468313707000},"page":"881-909","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Sparse multivariate polynomial interpolation on the basis of Schubert polynomials"],"prefix":"10.1007","volume":"26","author":[{"given":"Priyanka","family":"Mukhopadhyay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youming","family":"Qiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,12]]},"reference":[{"issue":"4","key":"142_CR1","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/s00037-010-0299-8","volume":"19","author":"Arvind Vikraman","year":"2010","unstructured":"Vikraman Arvind, Partha Mukhopadhyay, Srinivasan Srikanth (2010) New Results on Noncommutative and Commutative Polynomial Identity Testing. Computational Complexity 19(4): 521\u2013558","journal-title":"Computational Complexity"},{"key":"142_CR2","unstructured":"Sami Assaf, Nantel Bergeron & Frank Sottile (2014). A combinatorial proof that Schubert vs. Schur coefficients are nonnegative. arXiv preprint arXiv:1405.2603 ."},{"issue":"3","key":"142_CR3","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1006\/aama.1996.0508","volume":"18","author":"Barvinok Alexander","year":"1997","unstructured":"Alexander Barvinok, Fomin Sergey (1997) Sparse interpolation of symmetric polynomials. Advances in Applied Mathematics 18(3): 271\u2013285","journal-title":"Advances in Applied Mathematics"},{"key":"142_CR4","unstructured":"Michael Ben-Or & Prasoon Tiwari (1988). A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (Extended Abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2\u20134, 1988, Chicago, Illinois, USA, 301\u2013309.URL http:\/\/doi.acm.org\/10.1145\/62212.62241 ."},{"issue":"4","key":"142_CR5","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1080\/10586458.1993.10504567","volume":"2","author":"Bergeron Nantel","year":"1993","unstructured":"Nantel Bergeron, Billey Sara (1993) RC-graphs and Schubert polynomials. Experimental Mathematics 2(4): 257\u2013269","journal-title":"Experimental Mathematics"},{"key":"142_CR6","doi-asserted-by":"crossref","unstructured":"Nader H. Bshouty & Richard Cleve (1998). Interpolating Arithmetic Read-Once Formulas in Parallel. SIAM J. Comput. 27(2), 401\u2013413.","DOI":"10.1137\/S009753979528812X"},{"key":"142_CR7","unstructured":"Peter B\u00fcrgisser (2000). Completeness and reduction in algebraic complexity theory, volume 7. Springer Science & Business Media."},{"key":"142_CR8","doi-asserted-by":"crossref","unstructured":"Peter B\u00fcrgisser & Christian Ikenmeyer (2013). Deciding Positivity of Littlewood-Richardson Coefficients. SIAM J. Discrete Math. 27(4), 1639\u20131681 URL http:\/\/dx.doi.org\/10.1137\/120892532 .","DOI":"10.1137\/120892532"},{"key":"142_CR9","unstructured":"Cassio P de Campos, Georgios Stamoulis & Dennis Weyland (2013). A Structured View on Weighted Counting with Relations to Quantum Computation and Applications. In Electronic Colloquium on Computational Complexity (ECCC), volume 20, 133."},{"key":"142_CR10","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Neeraj Kayal & Satyanarayana V. Lokam (2011). Efficient Reconstruction of Random Multilinear Formulas. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22\u201325, 2011, 778\u2013787. URL http:\/\/dx.doi.org\/10.1109\/FOCS.2011.70 .","DOI":"10.1109\/FOCS.2011.70"},{"key":"142_CR11","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Neeraj Kayal & Satyanarayana V. Lokam (2012). Reconstruction of depth-4 multilinear circuits with top fan-in 2. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19\u201322, 2012, 625\u2013642. URL http:\/\/doi.acm.org\/10.1145\/2213977.2214035 .","DOI":"10.1145\/2213977.2214035"},{"key":"142_CR12","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Neeraj Kayal & Youming Qiao (2014). Random arithmetic formulas can be reconstructed efficiently. Computational Complexity 23(2), 207\u2013303. URL http:\/\/dx.doi.org\/10.1007\/s00037-014-0085-0 .","DOI":"10.1007\/s00037-014-0085-0"},{"key":"142_CR13","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen & Yagati N. Lakshman (1988). Improved Sparse Multivariate Polynomial Interpolation Algorithms. In Symbolic and Algebraic Computation, International Symposium ISSAC\u201988, Rome, Italy, July 4\u20138, 1988, Proceedings, Patrizia M. Gianni, editor, volume 358 of Lecture Notes in Computer Science, 467\u2013474. Springer. ISBN 3-540-51084-2. URL http:\/\/dx.doi.org\/10.1007\/3-540-51084-2_44 .","DOI":"10.1007\/3-540-51084-2_44"},{"key":"142_CR14","doi-asserted-by":"crossref","unstructured":"Zohar Shay Karnin & Amir Shpilka (2009). Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15\u201318 July 2009, 274\u2013285. URL http:\/\/dx.doi.org\/10.1109\/CCC.2009.18 .","DOI":"10.1109\/CCC.2009.18"},{"key":"142_CR15","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal (2012). Affine projections of polynomials: extended abstract. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19\u201322, 2012, 643\u2013662. URL http:\/\/doi.acm.org\/10.1145\/2213977.2214036 .","DOI":"10.1145\/2213977.2214036"},{"key":"142_CR16","doi-asserted-by":"crossref","unstructured":"Adalbert Kerber, Axel Kohnert & Alain Lascoux (1992). Symbolic Computation in Combinatorics SYMMETRICA, an object oriented computer-algebra system for the symmetric group. Journal of Symbolic Computation 14(2), 195 \u2013 203. ISSN 0747-7171. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/0747717192900353 .","DOI":"10.1016\/0747-7171(92)90035-3"},{"key":"142_CR17","unstructured":"Adam Klivans & Daniel A. Spielman (2001). Randomness efficient identity testing of multivariate polynomials. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6\u20138, 2001, Heraklion, Crete, Greece, 216\u2013223. URL http:\/\/doi.acm.org\/10.1145\/380752.380801 ."},{"key":"142_CR18","doi-asserted-by":"crossref","unstructured":"Allen Knutson & Ezra Miller (2005). Gr\u00f6bner Geometry of Schubert Polynomials. Annals of Mathematics 161(3), pp. 1245\u20131318. ISSN 0003486X. URL http:\/\/www.jstor.org\/stable\/3597357 .","DOI":"10.4007\/annals.2005.161.1245"},{"issue":"15","key":"142_CR19","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1155\/S1073792801000393","volume":"2001","author":"Mikhail Kogan","year":"2001","unstructured":"Kogan Mikhail (2001) RC-graphs and a generalized Littlewood-Richardson rule. International Mathematics Research Notices 2001(15): 765\u2013782","journal-title":"International Mathematics Research Notices"},{"key":"142_CR20","doi-asserted-by":"crossref","unstructured":"Pascal Koiran (2005). Valiant\u2019s model and the cost of computing integers. Computational Complexity 13(3\u20134), 131\u2013146. URL http:\/\/dx.doi.org\/10.1007\/s00037-004-0186-2 .","DOI":"10.1007\/s00037-004-0186-2"},{"key":"142_CR21","doi-asserted-by":"crossref","unstructured":"Alain Lascoux (2003). Symmetric functions and combinatorial operators on polynomials, volume 99. American Mathematical Soc.","DOI":"10.1090\/cbms\/099"},{"key":"142_CR22","unstructured":"Alain Lascoux (2008). Schubert and Macdonald polynomials, a parallel. Electronically available at http:\/\/igm.univ-mlv.fr\/~al\/ARTICLES\/Dummies.pdf ."},{"key":"142_CR23","unstructured":"Alain Lascoux (2013). Polynomials. Electronically available at http:\/\/igm.univ-mlv.fr\/~al\/ARTICLES\/CoursYGKM.pdf ."},{"key":"142_CR24","unstructured":"Alain Lascoux & Marcel-Paul Sch\u00fctzenberger (1982). Polyn\u00f4mes de Schubert. C. R. Acad. Sci. Paris S\u00e9r. I Math. 294(13), 447\u2013450"},{"key":"142_CR25","doi-asserted-by":"crossref","unstructured":"Alain Lascoux & Marcel-Paul Sch\u00fctzenberger (1985). Schubert polynomials and the Littlewood-Richardson rule. Letters in Mathematical Physics 10(2\u20133), 111\u2013124.","DOI":"10.1007\/BF00398147"},{"issue":"11","key":"142_CR26","doi-asserted-by":"crossref","first-page":"3319","DOI":"10.1090\/S0002-9939-03-06919-3","volume":"131","author":"Lenart Cristian","year":"2003","unstructured":"Cristian Lenart, Sottile Frank (2003) Skew Schubert polynomials. Proceedings of the American Mathematical Society 131(11): 3319\u20133328","journal-title":"Proceedings of the American Mathematical Society"},{"key":"142_CR27","unstructured":"Ian Grant Macdonald (1991). Notes on Schubert polynomials, volume 6. Montr\u00e9al: D\u00e9p. de math\u00e9matique et d\u2019informatique, Universit\u00e9 du Qu\u00e9bec \u00e0 Montr\u00e9al."},{"key":"142_CR28","unstructured":"L. Manivel (2001). Symmetric Functions, Schubert Polynomials, and Degeneracy Loci. Collection SMF.: Cours sp\u00e9cialis\u00e9s. American Mathematical Society. ISBN 9780821821541. URL http:\/\/books.google.com.au\/books?id=yz7gyKYgIuwC ."},{"key":"142_CR29","unstructured":"Karola M\u00e9sz\u00e1ros, Greta Panova & Alexander Postnikov (2014). Schur Times Schubert via the Fomin-Kirillov Algebra. Electr. J. Comb. 21(1), P1.39. URL http:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v21i1p39 ."},{"key":"142_CR30","doi-asserted-by":"crossref","unstructured":"Ketan Mulmuley (2011). On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakrishna. J. ACM 58(2), 5. URL http:\/\/doi.acm.org\/10.1145\/1944345.1944346 .","DOI":"10.1145\/1944345.1944346"},{"key":"142_CR31","doi-asserted-by":"crossref","unstructured":"Ketan D Mulmuley, Hariharan Narayanan & Milind Sohoni (2012). Geometric complexity theory III: on deciding nonvanishing of Littlewood-Richardson coefficient. Journal of Algebraic Combinatorics 36(1), 103\u2013110.","DOI":"10.1007\/s10801-011-0325-1"},{"issue":"3","key":"142_CR32","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10801-006-0008-5","volume":"24","author":"Narayanan Hariharan","year":"2006","unstructured":"Hariharan Narayanan (2006) On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients. Journal of Algebraic Combinatorics 24(3): 347\u2013354","journal-title":"Journal of Algebraic Combinatorics"},{"key":"142_CR33","unstructured":"R. Saptharishi (2016). A survey of lower bounds in arithmetic circuit complexity. URL https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases . Version 3.0.0."},{"issue":"6","key":"142_CR34","doi-asserted-by":"crossref","first-page":"2130","DOI":"10.1137\/070694879","volume":"38","author":"Shpilka Amir","year":"2009","unstructured":"Amir Shpilka (2009) Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. SIAM J. Comput. 38(6): 2130\u20132161","journal-title":"SIAM J. Comput."},{"key":"142_CR35","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Ilya Volkovich (2015). Read-once polynomial identity testing. Computational Complexity 24(3), 477\u2013532. URL http:\/\/dx.doi.org\/10.1007\/s00037-015-0105-8 .","DOI":"10.1007\/s00037-015-0105-8"},{"key":"142_CR36","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. http:\/\/dx.doi.org\/10.1561\/0400000039 .","DOI":"10.1561\/0400000039"},{"key":"142_CR37","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1979). Completeness Classes in Algebra. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard & Alfred V. Aho, editors, 249\u2013261. ACM. URL http:\/\/doi.acm.org\/10.1145\/800135.804419 .","DOI":"10.1145\/800135.804419"},{"key":"142_CR38","doi-asserted-by":"crossref","unstructured":"Richard Zippel (1979). Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, EdwardW. Ng, editor, volume 72 of Lecture Notes in Computer Science, 216\u2013226. Springer Berlin Heidelberg. ISBN 978-3-540-09519-4. URL http:\/\/dx.doi.org\/10.1007\/3-540-09519-5_73 .","DOI":"10.1007\/3-540-09519-5_73"},{"issue":"3","key":"142_CR39","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","volume":"9","author":"Zippel Richard","year":"1990","unstructured":"Richard Zippel (1990) Interpolating Polynomials from Their Values. J. Symb. Comput. 9(3): 375\u2013403","journal-title":"J. Symb. Comput."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0142-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0142-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0142-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0142-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,10]],"date-time":"2019-09-10T21:58:36Z","timestamp":1568152716000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0142-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,12]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["142"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0142-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,12]]}}}