{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T17:41:25Z","timestamp":1770831685324,"version":"3.50.1"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,2,28]]},"DOI":"10.1137\/24m1662084","type":"journal-article","created":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T08:26:16Z","timestamp":1767947176000},"page":"28-64","source":"Crossref","is-referenced-by-count":0,"title":["Linear Independence, Alternants and Applications"],"prefix":"10.1137","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-7869-377X","authenticated-orcid":true,"given":"Vishwas","family":"Bhargava","sequence":"first","affiliation":[{"name":"California Institute of Technology, Pasadena, CA 91125 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Department of Mathematics & Department of Computer Science, University of Toronto, Toronto, Canada."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7616-0751","authenticated-orcid":true,"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Boston College, Chestnut Hill, MA 02467 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2026,1,9]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/130910725"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"M. Agrawal and V. Vinay, Arithmetic circuits: A chasm at depth four, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008, pp. 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"key":"ref3","volume-title":"Determinants and Matrices","author":"Aitken A.","year":"2017"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003411"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0097-4"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.06.003"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.004"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337257"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"M. Ben-Or and P. Tiwari, A deterministic algorithm for sparse multivariate polynominal interpolation, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), 1988, pp. 301\u2013309.","DOI":"10.1145\/62212.62241"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"V. Bhargava, S. Saraf, and I. Volkovich, Reconstruction of depth-4 multilinear circuits, in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), S. Chawla, ed. 2020, pp. SIAM, 2144\u20132160.","DOI":"10.1137\/1.9781611975994.132"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"V. Bhargava, S. Saraf, and I. Volkovich, Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits, in STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, ACM, 2021, pp. 809\u2013822, https:\/\/doi.org\/10.1145\/3406325.3451096.","DOI":"10.1145\/3406325.3451096"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.4169\/000298910x515785"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-33275-6_15"},{"key":"ref15","series-title":"150 of LIPIcs","first-page":"11:1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Chatterjee P.","year":"2019"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"ref17","unstructured":"P. Dutta, P. Dwivedi, and N. Saxena, Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits, in Proceedings of the 36th Conference on Computational Complexity (CCC 2021), Vol. 5, 2021, 9."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"ref19","first-page":"115","author":"Forbes M. A.","year":"2012","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"ref20","series-title":"13 of LIPIcs","first-page":"127","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Grenet B.","year":"2011"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.012"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi, Arithmetic circuits: A chasm at depth three, in Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013, pp. 578\u2013587.","DOI":"10.1109\/FOCS.2013.68"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"A. Gupta, N. Kayal, and S. V. Lokam, Reconstruction of depth-4 multilinear circuits with top fanin 2, in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 2012, pp. 625\u2013642, https:\/\/eccc.weizmann.ac.il\/report\/2011\/153.","DOI":"10.1145\/2213977.2214035"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3169-1"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"J. Heintz and C. P. Schnorr, Testing polynomials which are easy to compute (extended abstract), in Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), 1980, pp. 262\u2013272.","DOI":"10.1145\/800141.804674"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"Z. S. Karnin and A. Shpilka, 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, pp. 274\u2013285, http:\/\/www.cs.technion.ac.il\/.","DOI":"10.1109\/CCC.2009.18"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2537-3"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"N. Kayal, Efficient algorithms for some special cases of the polynomial equivalence problem, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2011, pp. 1409\u20131421.","DOI":"10.1137\/1.9781611973082.108"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"N. Kayal and S. Saraf, Blackbox polynomial identity testing for depth 3 circuits, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009, pp. 198\u2013207, https:\/\/eccc.weizmann.ac.il\/report\/2009\/032.","DOI":"10.1109\/FOCS.2009.67"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a010"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"A. Klivans and D. Spielman, Randomness efficient identity testing of multivariate polynomials, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), 2001, pp. 216\u2013223.","DOI":"10.1145\/380752.380801"},{"key":"ref35","unstructured":"P. Koiran, Arithmetic Circuits: The Chasm at Depth Four Gets Wider, preprint, arXiv:1006.4700, 2010."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a006"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00083"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0167-5"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"S. Peleg and A. Shpilka, Polynomial time deterministic identity testing algorithm for \\(\\Sigma^{[3]}\\Pi \\Sigma \\Pi^{[2]}\\) circuits via Edelstein\u2013Kelly type theorem for quadratic polynomials, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 259\u2013271.","DOI":"10.1145\/3406325.3451013"},{"key":"ref40","unstructured":"S. Peleg, A. Shpilka, and B. Volk, Tensor reconstruction beyond constant rank, in Proceedings of the 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, LIPIcs 287, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024, pp. 87:1\u201387:20, 2024, https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2024.87."},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3460-4"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/090770679"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/10848232"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/2528403"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0105-8"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"ref48","unstructured":"G. Sinha, Reconstruction of real depth-3 circuits with top fan-in 2, in Proceedings of the 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, 2016, pp. 2016, 31:1\u201331:53, https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.31."},{"key":"ref49","first-page":"125","volume":"27","author":"Sinha G.","year":"2020","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90044-3"},{"key":"ref52","first-page":"943","volume-title":"APPROX-RANDOM","author":"Volkovich I.","year":"2015"},{"key":"ref53","first-page":"48:1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2017)","author":"Volkovich I.","year":"2017"},{"key":"ref54","doi-asserted-by":"crossref","unstructured":"R. Zippel, Probabilistic algorithms for sparse polynomials, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, Lecture Notes in Computer Science, Vol. 72, 1979, pp. 216\u2013226, https:\/\/doi.org\/10.1007\/3-540-09519-5_73.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T17:01:19Z","timestamp":1770829279000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1662084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,9]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2,28]]}},"alternative-id":["10.1137\/24M1662084"],"URL":"https:\/\/doi.org\/10.1137\/24m1662084","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,9]]}}}