{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T09:52:13Z","timestamp":1762249933898},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T00:00:00Z","timestamp":1691020800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T00:00:00Z","timestamp":1691020800000},"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,12]]},"DOI":"10.1007\/s00037-023-00239-8","type":"journal-article","created":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T08:02:29Z","timestamp":1691049749000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Absolute reconstruction for  sums of powers of linear forms: degree 3 and beyond"],"prefix":"10.1007","volume":"32","author":[{"given":"Pascal","family":"Koiran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhayan","family":"Saha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,3]]},"reference":[{"key":"239_CR1","unstructured":"Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M.\nKakade & Matus Telgarsky (2014). Tensor Decompositions\nfor Learning Latent Variable Models. Journal of Machine Learning\nResearch 15(80), 2773\u20132832. URL http:\/\/jmlr.org\/papers\/v15\/anandkumar14b.html."},{"key":"239_CR2","doi-asserted-by":"crossref","unstructured":"Erwin H. Bareiss (1968). Sylvester\u2019s Identity and Multistep\nInteger-Preserving Gaussian Elimination. Mathematics of Computation 22(103), 565\u2013578. ISSN 00255718, 10886842. URL http:\/\/www.jstor.org\/stable\/2004533.","DOI":"10.1090\/S0025-5718-1968-0226829-0"},{"key":"239_CR3","doi-asserted-by":"crossref","unstructured":"Alessandra Bernardi, Alessandro Gimigliano & Monica Ida\n(2011). Computing symmetric rank for symmetric tensors. Journal of\nSymbolic Computation 46(1), 34\u201353.","DOI":"10.1016\/j.jsc.2010.08.001"},{"key":"239_CR4","doi-asserted-by":"crossref","unstructured":"Vishwas Bhargava, Shubhangi Saraf & Ilya Volkovich (2021).\nReconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear\nCircuits. In Proceedings of the 53rd Annual ACM SIGACT Symposium\non Theory of Computing (STOC). URL https:\/\/doi.org\/10.1145\/3406325.3451096.","DOI":"10.1145\/3406325.3451096"},{"key":"239_CR5","doi-asserted-by":"crossref","unstructured":"Aditya Bhaskara, Moses Charikar, Ankur Moitra & Aravindan\nVijayaraghavan (2014). Smoothed Analysis of Tensor Decompositions.\nIn Proceedings of the Forty-Sixth Annual ACM Symposium\non Theory of Computing, STOC. URL https:\/\/doi.org\/10.1145\/2591796.2591881.","DOI":"10.1145\/2591796.2591881"},{"key":"239_CR6","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub & S. Smale (1998). Complexity and\nReal Computation. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"239_CR7","doi-asserted-by":"crossref","unstructured":"L. Blum, M. Shub & S. Smale (1989). On a theory of computation\nand complexity over the real numbers: NP-completeness, recursive functions\nand universal machines. Bulletin of the American Mathematical\nSociety 21(1), 1\u201346.","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"239_CR8","doi-asserted-by":"crossref","unstructured":"Jrme Brachat, Pierre Comon, Bernard Mourrain & Elias Tsigaridas\n(2010). Symmetric tensor decomposition. Linear Algebra and\nits Applications 433(11-12), 1851\u20131872","DOI":"10.1016\/j.laa.2010.06.046"},{"key":"239_CR9","doi-asserted-by":"crossref","unstructured":"Enrico Carlini (2006). Reducing the number of variables of a\npolynomial. In Algebraic geometry and geometric modeling, Math.\nVis., 237\u2013247. Springer, Berlin. URL https:\/\/doi.org\/10.1007\/978-3-540-33275-6_15.","DOI":"10.1007\/978-3-540-33275-6_15"},{"key":"239_CR10","doi-asserted-by":"crossref","unstructured":"Guillaume Cheze & Andr\u00e9 Galligo (2005). Four lectures on polynomial\nabsolute factorization. In Solving polynomial equations, 339\u2013392.\nSpringer.","DOI":"10.1007\/3-540-27357-3_9"},{"key":"239_CR11","doi-asserted-by":"crossref","unstructured":"Guillaume Ch\u00e9ze & Gr\u00e9goire Lecerf (2007). Lifting and recombination\ntechniques for absolute factorization. Journal of Complexity\n23(3), 380\u2013420.","DOI":"10.1016\/j.jco.2007.01.008"},{"key":"239_CR12","doi-asserted-by":"crossref","unstructured":"Richard A. Demillo & Richard J. Lipton (1978). A probabilistic\nremark on algebraic program testing. Information Processing Letters\n7(4), 193\u2013195. URL https:\/\/www.sciencedirect.com\/science\/article\/pii\/0020019078900674.","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"239_CR13","unstructured":"Michael A. Forbes, Sumanta Ghosh & Nitin Saxena (2018).\nTowards Blackbox Identity Testing of Log-Variate Circuits. In 45th\nInternational Colloquium on Automata, Languages, and Programming\n(ICALP 2018). URL http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9058."},{"key":"239_CR14","doi-asserted-by":"crossref","unstructured":"R\u016bsi\u0146\u0161 Freivalds (1979). Fast probabilistic algorithms. In International\nSymposium on Mathematical Foundations of Computer Science\n(MFCS), 57\u201369. Springer.","DOI":"10.1007\/3-540-09526-8_5"},{"key":"239_CR15","doi-asserted-by":"crossref","unstructured":"Shuhong Gao (2003). Factoring multivariate polynomials via partial\ndifferential equations. Mathematics of computation 72(242), 801\u2013822.","DOI":"10.1090\/S0025-5718-02-01428-X"},{"key":"239_CR16","doi-asserted-by":"crossref","unstructured":"Ignacio Garc\u00eda-Marco, Pascal Koiran & Timoth\u00e9e Pecatte\n(2017). Reconstruction Algorithms for Sums of Affine Powers. In\nProc. International Symposium on Symbolic and Algebraic Computation\n(ISSAC), 317\u2013324. URL http:\/\/doi.acm.org\/10.1145\/3087604.3087605.","DOI":"10.1145\/3087604.3087605"},{"key":"239_CR17","doi-asserted-by":"crossref","unstructured":"Ignacio Garc\u00eda-Marco, Pascal Koiran & Timoth\u00e9e Pecatte\n(2018). Polynomial equivalence problems for sums of affine powers. In\nProc. International Symposium on Symbolic and Algebraic Computation\n(ISSAC).","DOI":"10.1145\/3208976.3208993"},{"key":"239_CR18","unstructured":"Ankit Garg, Nikhil Gupta, Neeraj Kayal & Chandan Saha\n(2019). Determinant Equivalence Test over Finite Fields and over Q.\nIn 46th International Colloquium on Automata, Languages, and Programming\n(ICALP 2019). URL http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10638."},{"key":"239_CR19","doi-asserted-by":"crossref","unstructured":"Joachim von zur Gathen & J\u00a8urgen Gerhard (2013). Modern\nComputer Algebra. Cambridge University Press, USA, 3rd edition.","DOI":"10.1017\/CBO9781139856065"},{"key":"239_CR20","unstructured":"Richard Harshman (1970). Foundations of the PARAFAC procedure:\nModels and conditions for an \u201dexplanatory\u201d multimodal factor analysis.\nUCLA working papers in phonetics ."},{"key":"239_CR21","unstructured":"Roger Horn & Charles Johnson (2013). Matrix Analysis. Cambridge\nUniversity Press (second edition)."},{"key":"239_CR22","doi-asserted-by":"crossref","unstructured":"Zohar Karnin & Amir Shpilka (2009). Reconstruction of generalized\ndepth-3 arithmetic circuits with bounded top fan-in. In 24th Annual\nIEEE Conference on Computational Complexity (CCC), 274\u2013285.","DOI":"10.1109\/CCC.2009.18"},{"key":"239_CR23","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal (2011). Efficient algorithms for some special cases of the\npolynomial equivalence problem. In Symposium on Discrete Algorithms\n(SODA). Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973082.108"},{"key":"239_CR24","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal, Vineet Nair, Chandan Saha & S\u00e9bastien Tavenas\n(2018). Reconstruction of full rank algebraic branching programs.\nACM Transactions on Computation Theory (TOCT) 11(1), 2.","DOI":"10.1145\/3282427"},{"key":"239_CR25","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal & Chandan Saha (2019). Reconstruction of nondegenerate\nhomogeneous depth three circuits. In Proc. 51st Annual\nACM Symposium on Theory of Computing (STOC), 413\u2013424.","DOI":"10.1145\/3313276.3316360"},{"key":"239_CR26","doi-asserted-by":"crossref","unstructured":"Walter Keller-Gehrig (1985). Fast algorithms for the characteristics\npolynomial. Theoretical Computer Science 36, 309 \u2013 317. ISSN\n0304-3975. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/0304397585900490.","DOI":"10.1016\/0304-3975(85)90049-0"},{"key":"239_CR27","unstructured":"Pascal Koiran & Subhayan Saha (2022). Black Box Absolute Reconstruction\nfor Sums of Powers of Linear Forms. In 42nd IARCS Annual\nConference on Foundations of Software Technology and Theoretical\nComputer Science (FSTTCS 2022). URL https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2022\/17416."},{"key":"239_CR28","doi-asserted-by":"crossref","unstructured":"Pascal Koiran & Subhayan Saha (2023). Complete Decomposition\nof Symmetric Tensors in Linear Time and Polylogarithmic Precision.\nIn 13th International Conference on Algorithms and Complexity (CIAC\n2023). URL https:\/\/arxiv.org\/abs\/2211.07407.","DOI":"10.1007\/978-3-031-30448-4_22"},{"key":"239_CR29","doi-asserted-by":"crossref","unstructured":"Pascal Koiran & Mateusz Skomra (2021). Derandomization and\nabsolute reconstruction for sums of powers of linear forms. Theoretical\nComputer Science 887, 63\u201384.","DOI":"10.1016\/j.tcs.2021.07.005"},{"key":"239_CR30","doi-asserted-by":"crossref","unstructured":"T. Kolda & B. Bader (2009). Tensor Decompositions and Applications.\nSIAM Rev. 51, 455\u2013500.","DOI":"10.1137\/07070111X"},{"key":"239_CR31","doi-asserted-by":"crossref","unstructured":"Fr\u00e9d\u00e9ric Magniez & Ashwin Nayak (2007). Quantum complexity\nof testing group commutativity. Algorithmica 48(3), 221\u2013232.","DOI":"10.1007\/s00453-007-0057-8"},{"key":"239_CR32","doi-asserted-by":"crossref","unstructured":"A. Moitra (2018). Algorithmic Aspects of Machine Learning. Cambridge\nUniversity Press. URL https:\/\/books.google.fr\/books?id=ruVqDwAAQBAJ.","DOI":"10.1017\/9781316882177"},{"key":"239_CR33","doi-asserted-by":"crossref","unstructured":"Igor Pak (2012). Testing commutativity of a group and the power\nof randomization. LMS Journal of Computation and Mathematics 15,\n38\u201343.","DOI":"10.1112\/S1461157012000046"},{"key":"239_CR34","unstructured":"Shir Peleg, Amir Shpilka & Ben Lee Volk (2022). Tensor Reconstruction\nBeyond Constant Rank."},{"key":"239_CR35","doi-asserted-by":"crossref","unstructured":"Sridhar Rajagopalan & Leonard J. Schulman (2000). Verification\nof Identities. SIAM Journal on Computing 29(4), 1155\u20131163. URL\nhttps:\/\/doi.org\/10.1137\/S0097539797325387.","DOI":"10.1137\/S0097539797325387"},{"key":"239_CR36","doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage & V. Strassen (1971). Schnelle Multiplikation gro\u00dfer\nZahlen. Computing 7(3), 281\u2013292. URL https:\/\/doi.org\/10.1007\/BF02242355.","DOI":"10.1007\/BF02242355"},{"key":"239_CR37","doi-asserted-by":"crossref","unstructured":"J. T. Schwartz (1980). Fast Probabilistic Algorithms for Verification\nof Polynomial Identities. J. ACM 27(4), 701-717. URL https:\/\/doi.org\/10.1145\/322217.322225.","DOI":"10.1145\/322217.322225"},{"key":"239_CR38","doi-asserted-by":"crossref","unstructured":"Hani Shaker (2009). Topology and factorization of polynomials.\nMathematica Scandinavica 51\u201359.","DOI":"10.7146\/math.scand.a-15084"},{"key":"239_CR39","unstructured":"Yaroslav Shitov (2016). How hard is the tensor rank? arXiv preprint\narXiv:1611.01559 ."},{"key":"239_CR40","doi-asserted-by":"crossref","unstructured":"Amir Shpilka (2009). Interpolation of depth-3 arithmetic circuits with\ntwo multiplication gates. SIAM Journal on Computing 38(6), 2130\u2013\n2161.","DOI":"10.1137\/070694879"},{"key":"239_CR41","doi-asserted-by":"crossref","unstructured":"Richard Zippel (1979). Probabilistic algorithms for sparse polynomials.\nIn Symbolic and Algebraic Computation, 216\u2013226. Springer Berlin\nHeidelberg, Berlin, Heidelberg.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00239-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00239-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00239-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T19:03:59Z","timestamp":1703617439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00239-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,3]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["239"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00239-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,3]]},"assertion":[{"value":"17 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"8"}}