{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:36:44Z","timestamp":1787236604733,"version":"build-2736575974"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T00:00:00Z","timestamp":1787184000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T00:00:00Z","timestamp":1787184000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100031755","name":"Reichman University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100031755","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2026,12]]},"abstract":"Abstract<\/jats:title>\n \n We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results:\n \n \n \n A randomized algorithm that reconstructs polynomials computed by multilinear\n \n \n $$\\Sigma ^{[k]}\\prod ^{[d]}\\Sigma $$<\/jats:tex-math>\n \n \n \n \u03a3<\/mml:mi>\n \n [<\/mml:mo>\n k<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u220f<\/mml:mo>\n \n [<\/mml:mo>\n d<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \u03a3<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n circuits in time\n \n \n $$\\textsf{poly}(n,d,c) \\cdot k^{k^{k^{k^{O(k)}}}}$$<\/jats:tex-math>\n \n \n poly<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n d<\/mml:mi>\n ,<\/mml:mo>\n c<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n k<\/mml:mi>\n \n k<\/mml:mi>\n \n k<\/mml:mi>\n \n k<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:msup>\n <\/mml:msup>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n <\/jats:p>\n <\/jats:list-item>\n \n \n A randomized algorithm that reconstructs polynomials computed by set-multilinear\n \n \n $$\\Sigma ^{[k]}\\prod ^{[d]}\\Sigma $$<\/jats:tex-math>\n \n \n \n \u03a3<\/mml:mi>\n \n [<\/mml:mo>\n k<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u220f<\/mml:mo>\n \n [<\/mml:mo>\n d<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \u03a3<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n circuits in time\n \n \n $$\\textsf{poly}(n,d,c) \\cdot k^{k^{k^{k^{O(k)}}}}$$<\/jats:tex-math>\n \n \n poly<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n d<\/mml:mi>\n ,<\/mml:mo>\n c<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n k<\/mml:mi>\n \n k<\/mml:mi>\n \n k<\/mml:mi>\n \n k<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:msup>\n <\/mml:msup>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n where\n \n \n $$c=\\log q$$<\/jats:tex-math>\n \n \n c<\/mml:mi>\n =<\/mml:mo>\n log<\/mml:mo>\n q<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n if\n \n \n $$\\mathbb {F}=\\mathbb {F}_q$$<\/jats:tex-math>\n \n \n F<\/mml:mi>\n =<\/mml:mo>\n \n F<\/mml:mi>\n q<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is a finite field, and\n c<\/jats:italic>\n equals the maximum bit complexity of any coefficient of\n f<\/jats:italic>\n if\n \n \n $$\\mathbb {F}$$<\/jats:tex-math>\n \n F<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is infinite.\n <\/jats:p>\n \n Prior to our work, polynomial-time algorithms for the case when the rank,\n k<\/jats:italic>\n , is constant, were given by Bhargava et al. (2021).\n <\/jats:p>\n \n Another contribution of this work is correcting an error from a paper of Karnin and Shpilka (2009) (with some loss in parameters) that also affected Theorem 1.6 of Bhargava et al. (2021). Consequently, the results of Karnin and Shpilka (2009); Bhargava et al. (2021) continue to hold, with a slightly worse setting of parameters. For fixing the error, we systematically study the relation between syntactic and semantic notions of rank of\n \n \n $$\\Sigma \\Pi \\Sigma $$<\/jats:tex-math>\n \n \n \u03a3<\/mml:mi>\n \u03a0<\/mml:mi>\n \u03a3<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n circuits, and the corresponding partitions of such circuits.\n <\/jats:p>\n \n We obtain our improved running time by introducing a technique for learning rank-preserving coordinate-subspaces. Both Karnin and Shpilka (2009) and Bhargava et al. (2021) tried all choices of finding the \u201ccorrect\u201d coordinates, which, due to the size of the set, led to having a fast growing function of\n k<\/jats:italic>\n at the exponent of\n n<\/jats:italic>\n . We manage to find these spaces in time that is still growing fast with\n k<\/jats:italic>\n , yet it is only a fixed polynomial in\n n<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1007\/s00037-026-00295-w","type":"journal-article","created":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T13:56:15Z","timestamp":1787234175000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tensor reconstruction beyond constant rank"],"prefix":"10.1007","volume":"35","author":[{"given":"Shir","family":"Peleg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ben Lee","family":"Volk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,20]]},"reference":[{"issue":"3","key":"295_CR1","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1137\/140975103","volume":"44","author":"Manindra Agrawal","year":"2015","unstructured":"Manindra Agrawal, Rohit Gurjar, Arpita Korwar & Nitin Saxena (2015). Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM Journal of Computing 44(3), 669\u2013697. https:\/\/doi.org\/10.1137\/140975103.","journal-title":"SIAM Journal of Computing"},{"key":"295_CR2","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal & V.\u00a0Vinay (2008). Arithmetic Circuits: A Chasm at Depth Four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"key":"295_CR3","doi-asserted-by":"publisher","unstructured":"Michael Ben-Or & Prasoon Tiwari (1988). A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation (Extended Abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988), 301\u2013309. ACM. https:\/\/doi.org\/10.1145\/62212.62241.","DOI":"10.1145\/62212.62241"},{"key":"295_CR4","doi-asserted-by":"publisher","unstructured":"Vishwas Bhargava, Shubhangi Saraf & Ilya Volkovich (2020). Reconstruction of Depth-4 Multilinear Circuits. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), 2144\u20132160. SIAM. https:\/\/doi.org\/10.1137\/1.9781611975994.132.","DOI":"10.1137\/1.9781611975994.132"},{"key":"295_CR5","doi-asserted-by":"publisher","unstructured":"Vishwas Bhargava, Shubhangi Saraf & Ilya Volkovich (2021). Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021), 809\u2013822. ACM. https:\/\/doi.org\/10.1145\/3406325.3451096.","DOI":"10.1145\/3406325.3451096"},{"key":"295_CR6","doi-asserted-by":"crossref","unstructured":"Vishwas Bhargava & Devansh Shringi (2024). Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. Electron. Colloquium Comput. Complex. TR24-123. https:\/\/eccc.weizmann.ac.il\/report\/2024\/123.","DOI":"10.1007\/s40278-024-66105-2"},{"key":"295_CR7","doi-asserted-by":"publisher","unstructured":"Markus Bl\u00e4ser, Christian Ikenmeyer, Gorav Jindal & Vladimir Lysikov (2018). Generalized matrix completion and algebraic natural proofs. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), 1193\u20131206. ACM. https:\/\/doi.org\/10.1145\/3188745.3188832.","DOI":"10.1145\/3188745.3188832"},{"key":"295_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40935-6_4","author":"Nader H. Bshouty (2013). Exact Learning from Membership Queries: Some Techniques, Results and New Directions. In Algorithmic Learning Theory - 24th International Conference, ALT","year":"2013","unstructured":"Nader\u00a0H. Bshouty (2013). Exact Learning from Membership Queries: Some Techniques, Results and New Directions. In Algorithmic Learning Theory - 24th International Conference, ALT 2013, volume 8139 of Lecture Notes in Computer Science, 33\u201352. Springer. https:\/\/doi.org\/10.1007\/978-3-642-40935-6_4.","journal-title":"Springer"},{"key":"295_CR9","doi-asserted-by":"crossref","unstructured":"Enrico Carlini (2006). Reducing the number of variables of a polynomial. In Algebraic Geometry and Geometric Modeling, 237\u2013247. ISBN 978-3-540-33275-6.","DOI":"10.1007\/978-3-540-33275-6_15"},{"key":"295_CR10","unstructured":"David\u00a0A. Cox, John\u00a0B. Little & Donal O\u2019Shea (2007). Ideals, Varieties and Algorithms. Undergraduate texts in mathematics. Springer."},{"key":"295_CR11","doi-asserted-by":"publisher","unstructured":"Zeev Dvir & Amir Shpilka (2007). Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits. SIAM J. Comput. 36(5), 1404\u20131434. https:\/\/doi.org\/10.1137\/05063605X. Preliminary version in the 37th Annual ACM Symposium on Theory of Computing (STOC 2005).","DOI":"10.1137\/05063605X"},{"key":"295_CR12","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.54","author":"Michael A. Forbes, Sumanta Ghosh & Nitin Saxena (2018). Towards Blackbox Identity Testing of Log-Variate Circuits. In Preliminary version in the 45th International Colloquium on Automata, Languages and Programming (ICALP","year":"2018","unstructured":"Michael\u00a0A. Forbes, Sumanta Ghosh & Nitin Saxena (2018). Towards Blackbox Identity Testing of Log-Variate Circuits. In Preliminary version in the 45th International Colloquium on Automata, Languages and Programming (ICALP 2018), volume 107 of LIPIcs, 54:1\u201354:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.54.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"295_CR13","doi-asserted-by":"publisher","unstructured":"Michael\u00a0A. Forbes, Ramprasad Saptharishi & Amir Shpilka (2014). Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), 867\u2013875. https:\/\/doi.org\/10.1145\/2591796.2591816.","DOI":"10.1145\/2591796.2591816"},{"key":"295_CR14","doi-asserted-by":"publisher","unstructured":"Michael\u00a0A. Forbes & Amir Shpilka (2013). Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), 243\u2013252. https:\/\/doi.org\/10.1109\/FOCS.2013.34. Full version at arXiv:1209.2408.","DOI":"10.1109\/FOCS.2013.34"},{"key":"295_CR15","doi-asserted-by":"publisher","unstructured":"Ankit Garg, Neeraj Kayal & Chandan Saha (2020). Learning sums of powers of low-degree polynomials in the non-degenerate case. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), 889\u2013899. IEEE. https:\/\/doi.org\/10.1109\/FOCS46700.2020.00087.","DOI":"10.1109\/FOCS46700.2020.00087"},{"key":"295_CR16","doi-asserted-by":"publisher","unstructured":"Zeyu Guo & Rohit Gurjar (2020). Improved Explicit Hitting-Sets for ROABPs. In Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM 2020), volume 176 of LIPIcs, 4:1\u20134:16. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.4.","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.4"},{"issue":"3","key":"295_CR17","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1137\/140957123","volume":"45","author":"Ankit Gupta","year":"2016","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2016). Arithmetic Circuits: A Chasm at Depth 3. SIAM J. Comput. 45(3), 1064\u20131079. https:\/\/doi.org\/10.1137\/140957123.","journal-title":"SIAM J. Comput."},{"key":"295_CR18","doi-asserted-by":"publisher","unstructured":"Ankit Gupta, Neeraj Kayal & Satyanarayana\u00a0V. Lokam (2011). Efficient Reconstruction of Random Multilinear Formulas. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), 778\u2013787. IEEE Computer Society. https:\/\/doi.org\/10.1109\/FOCS.2011.70.","DOI":"10.1109\/FOCS.2011.70"},{"key":"295_CR19","doi-asserted-by":"publisher","unstructured":"Ankit Gupta, Neeraj Kayal & Satyanarayana\u00a0V. Lokam (2012). Reconstruction of depth-4 multilinear circuits with top fan-in 2. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012), 625\u2013642. ACM. https:\/\/doi.org\/10.1145\/2213977.2214035.","DOI":"10.1145\/2213977.2214035"},{"issue":"4","key":"295_CR20","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1016\/0196-6774(90)90014-6","volume":"11","author":"Johan H\u00e5stad","year":"1990","unstructured":"Johan H\u00e5stad (1990). Tensor Rank is NP-Complete. J. Algorithms 11(4), 644\u2013654. https:\/\/doi.org\/10.1016\/0196-6774(90)90014-6.","journal-title":"J. Algorithms"},{"issue":"3","key":"295_CR21","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","volume":"9","author":"Erich Kaltofen","year":"1990","unstructured":"Erich Kaltofen & Barry\u00a0M. Trager (1990). Computing with Polynomials Given By Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators. J. Symb. Comput. 9(3), 301\u2013320. https:\/\/doi.org\/10.1016\/S0747-7171(08)80015-6.","journal-title":"J. Symb. Comput."},{"issue":"6","key":"295_CR22","doi-asserted-by":"publisher","first-page":"2114","DOI":"10.1137\/110824516","volume":"42","author":"Zohar Shay Karnin","year":"2013","unstructured":"Zohar\u00a0Shay Karnin, Partha Mukhopadhyay, Amir Shpilka & Ilya Volkovich (2013). Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in. SIAM J. Comput. 42(6), 2114\u20132131. https:\/\/doi.org\/10.1137\/110824516.","journal-title":"SIAM J. Comput."},{"key":"295_CR23","doi-asserted-by":"publisher","unstructured":"Zohar\u00a0Shay Karnin & Amir Shpilka (2008). Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, 280\u2013291. IEEE Computer Society. https:\/\/doi.org\/10.1109\/CCC.2008.15.","DOI":"10.1109\/CCC.2008.15"},{"key":"295_CR24","doi-asserted-by":"publisher","unstructured":"Zohar\u00a0Shay 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), 274\u2013285. IEEE Computer Society. https:\/\/doi.org\/10.1109\/CCC.2009.18.","DOI":"10.1109\/CCC.2009.18"},{"key":"295_CR25","doi-asserted-by":"publisher","unstructured":"Neeraj Kayal (2011). Efficient algorithms for some special cases of the polynomial equivalence problem. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 1409\u20131421. SIAM. https:\/\/doi.org\/10.1137\/1.9781611973082.108.","DOI":"10.1137\/1.9781611973082.108"},{"key":"295_CR26","doi-asserted-by":"publisher","unstructured":"Neeraj Kayal (2012). Affine projections of polynomials: extended abstract. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012), 643\u2013662. ACM. https:\/\/doi.org\/10.1145\/2213977.2214036.","DOI":"10.1145\/2213977.2214036"},{"issue":"4","key":"295_CR27","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1007\/s00037-019-00189-0","volume":"28","author":"Neeraj Kayal","year":"2019","unstructured":"Neeraj Kayal, Vineet Nair & Chandan Saha (2019). Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. Comput. Complex. 28(4), 749\u2013828. https:\/\/doi.org\/10.1007\/s00037-019-00189-0.","journal-title":"Comput. Complex."},{"key":"295_CR28","doi-asserted-by":"publisher","unstructured":"Neeraj Kayal & Shubhangi Saraf (2009). Blackbox polynomial identity testing for depth-$$3$$ circuits. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009). https:\/\/doi.org\/10.1109\/FOCS.2009.67.","DOI":"10.1109\/FOCS.2009.67"},{"key":"295_CR29","doi-asserted-by":"crossref","unstructured":"Adam Klivans & Daniel\u00a0A. Spielman (2001). Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC 2001), 216\u2013223.","DOI":"10.1145\/380752.380801"},{"key":"295_CR30","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","volume":"448","author":"Pascal Koiran","year":"2012","unstructured":"Pascal Koiran (2012). Arithmetic Circuits: The Chasm at Depth Four Gets Wider. Theoretical Computer Science 448, 56\u201365.","journal-title":"Theoretical Computer Science"},{"key":"295_CR31","doi-asserted-by":"publisher","unstructured":"Shir Peleg, Amir Shpilka & Ben\u00a0Lee Volk (2024). Tensor Reconstruction Beyond Constant Rank. In 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, volume 287 of LIPIcs, 87:1\u201387:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2024.87.","DOI":"10.4230\/LIPIcs.ITCS.2024.87"},{"issue":"1","key":"295_CR32","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1137\/090770679","volume":"40","author":"Nitin Saxena","year":"2011","unstructured":"Nitin Saxena & C.\u00a0Seshadhri (2011). An Almost Optimal Rank Bound for Depth-3 Identities. SIAM J. Comput. 40(1), 200\u2013224. https:\/\/doi.org\/10.1137\/090770679.","journal-title":"SIAM J. Comput."},{"key":"295_CR33","doi-asserted-by":"publisher","unstructured":"Nitin Saxena & C.\u00a0Seshadhri (2012). Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn\u2019t Matter. SIAM J. Comput. 41(5), 1285\u20131298. https:\/\/doi.org\/10.1137\/10848232. Preliminary version in the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011).","DOI":"10.1137\/10848232"},{"key":"295_CR34","doi-asserted-by":"publisher","unstructured":"Nitin Saxena & C.\u00a0Seshadhri (2013). From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM 60(5), 33:1\u201333:33. https:\/\/doi.org\/10.1145\/2528403.","DOI":"10.1145\/2528403"},{"key":"295_CR35","unstructured":"Yaroslav Shitov (2016). How hard is the tensor rank? arXiv preprint arXiv:1611.01559"},{"key":"295_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.","DOI":"10.1561\/0400000039"},{"key":"295_CR37","doi-asserted-by":"publisher","unstructured":"Gaurav Sinha (2016). Reconstruction of Real Depth-3 Circuits with Top Fan-In 2. In Proceedings of the 31st Annual Computational Complexity Conference (CCC 2016), volume\u00a050 of LIPIcs, 31:1\u201331:53. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.31.","DOI":"10.4230\/LIPIcs.CCC.2016.31"},{"key":"295_CR38","doi-asserted-by":"publisher","unstructured":"Gaurav Sinha (2022). Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Mark Braverman, editor, volume 215 of LIPIcs, 118:1\u2013118:33. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2022.118.","DOI":"10.4230\/LIPIcs.ITCS.2022.118"},{"key":"295_CR39","doi-asserted-by":"publisher","unstructured":"Joseph Swernofsky (2018). Tensor Rank is Hard to Approximate. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2018, volume 116 of LIPIcs, 26:1\u201326:9. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.26.","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.26"},{"key":"295_CR40","doi-asserted-by":"crossref","unstructured":"S\u00e9bastien Tavenas (2015). Improved bounds for reduction to depth 4 and depth 3. Inf. Comput. 240, 2\u201311. Preliminary version in the 38th International Symposium on the Mathematical Foundations of Computer Science (MFCS 2013).","DOI":"10.1007\/978-3-642-40313-2_71"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-026-00295-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-026-00295-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-026-00295-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T13:56:25Z","timestamp":1787234185000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-026-00295-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,20]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["295"],"URL":"https:\/\/doi.org\/10.1007\/s00037-026-00295-w","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,20]]},"assertion":[{"value":"11 June 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2026","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}