{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:37Z","timestamp":1750309477498,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Sloan research fellowship and an NSERC Discovery Grant.","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585149","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"441-454","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Linear Independence, Alternants, and Applications"],"prefix":"10.1145","author":[{"given":"Vishwas","family":"Bhargava","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}]},{"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[{"name":"Boston College, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/130910725"},{"volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 67\u201375","author":"Agrawal M.","key":"e_1_3_2_1_2_1","unstructured":"M. Agrawal and V. Vinay . 2008. Arithmetic circuits: A chasm at depth four . In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 67\u201375 . M. Agrawal and V. Vinay. 2008. Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 67\u201375."},{"volume-title":"Determinants and matrices","author":"Aitken Alexander Craig","key":"e_1_3_2_1_3_1","unstructured":"Alexander Craig Aitken . 2017. Determinants and matrices . Read Books Ltd . Alexander Craig Aitken. 2017. Determinants and matrices. Read Books Ltd."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/971651.971653"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0097-4"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.06.003"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.004"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337257"},{"volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC). 301\u2013309","author":"Ben-Or M.","key":"e_1_3_2_1_10_1","unstructured":"M. Ben-Or and P. Tiwari . 1988. A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation . In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC). 301\u2013309 . M. Ben-Or and P. Tiwari. 1988. A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC). 301\u2013309."},{"volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Shuchi Chawla (Ed.). SIAM, 2144\u20132160","author":"Bhargava V.","key":"e_1_3_2_1_11_1","unstructured":"V. Bhargava , S. Saraf , and I. Volkovich . 2020. Reconstruction of Depth-4 Multilinear Circuits . In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Shuchi Chawla (Ed.). SIAM, 2144\u20132160 . V. Bhargava, S. Saraf, and I. Volkovich. 2020. Reconstruction of Depth-4 Multilinear Circuits. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Shuchi Chawla (Ed.). SIAM, 2144\u20132160."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451096"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4169\/000298910x515785"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-33275-6_15"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2019.11"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_1_17_1","volume-title":"36th Conference on Computational Complexity (CCC","author":"Dutta P.","year":"2021","unstructured":"P. Dutta , P. Dwivedi , and N. Saxena . 2021. Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits . In 36th Conference on Computational Complexity (CCC 2021 ). 5, 9. P. Dutta, P. Dwivedi, and N. Saxena. 2021. Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits. In 36th Conference on Computational Complexity (CCC 2021). 5, 9."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"e_1_3_2_1_19_1","first-page":"115","article-title":"Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs","volume":"19","author":"Forbes M. A.","year":"2012","unstructured":"M. A. Forbes and A. Shpilka . 2012 . Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs . Electronic Colloquium on Computational Complexity (ECCC) , 19 (2012), 115 . M. A. Forbes and A. Shpilka. 2012. Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. Electronic Colloquium on Computational Complexity (ECCC), 19 (2012), 115.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90044-3"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2011.127"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.012"},{"volume-title":"Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 578\u2013587","author":"Gupta A.","key":"e_1_3_2_1_23_1","unstructured":"A. Gupta , P. Kamath , N. Kayal , and R. Saptharishi . 2013. Arithmetic Circuits: A Chasm at Depth Three . In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 578\u2013587 . A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. 2013. Arithmetic Circuits: A Chasm at Depth Three. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 578\u2013587."},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). 625\u2013642","author":"Gupta A.","year":"2011","unstructured":"A. Gupta , N. Kayal , and S. V. Lokam . 2012. Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2 . In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). 625\u2013642 . Full version at https:\/\/eccc.weizmann.ac.il\/report\/ 2011 \/153. A. Gupta, N. Kayal, and S. V. Lokam. 2012. Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). 625\u2013642. Full version at https:\/\/eccc.weizmann.ac.il\/report\/2011\/153."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3169-1"},{"volume-title":"Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC). 262\u2013272","author":"Heintz J.","key":"e_1_3_2_1_26_1","unstructured":"J. Heintz and C. P. Schnorr . 1980. Testing Polynomials which Are Easy to Compute (Extended Abstract) . In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC). 262\u2013272 . J. Heintz and C. P. Schnorr. 1980. Testing Polynomials which Are Easy to Compute (Extended Abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC). 262\u2013272."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"volume-title":"Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC). 274\u2013285","author":"Karnin Z. S.","key":"e_1_3_2_1_29_1","unstructured":"Z. S. Karnin and A. 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). 274\u2013285 . Full version at http:\/\/www.cs.technion.ac.il\/ shpilka\/publications\/KarninShpilka09.pdf. Z. S. Karnin and A. 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). 274\u2013285. Full version at http:\/\/www.cs.technion.ac.il\/ shpilka\/publications\/KarninShpilka09.pdf."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2537-3"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.108"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 198\u2013207","author":"Kayal N.","year":"2009","unstructured":"N. Kayal and S. Saraf . 2009. Blackbox Polynomial Identity Testing for Depth 3 Circuits . In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 198\u2013207 . Full version at https:\/\/eccc.weizmann.ac.il\/report\/ 2009 \/032. N. Kayal and S. Saraf. 2009. Blackbox Polynomial Identity Testing for Depth 3 Circuits. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 198\u2013207. Full version at https:\/\/eccc.weizmann.ac.il\/report\/2009\/032."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"A. Klivans and A. Shpilka. 2006. Learning restricted models of arithmetic circuits.. Theory of computing 2 10 (2006) 185\u2013206. \t\t\t\t  A. Klivans and A. Shpilka. 2006. Learning restricted models of arithmetic circuits.. Theory of computing 2 10 (2006) 185\u2013206.","DOI":"10.4086\/toc.2006.v002a010"},{"volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). 216\u2013223","author":"Klivans A.","key":"e_1_3_2_1_35_1","unstructured":"A. Klivans and D. Spielman . 2001. Randomness efficient identity testing of multivariate polynomials . In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). 216\u2013223 . A. Klivans and D. Spielman. 2001. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). 216\u2013223."},{"key":"e_1_3_2_1_36_1","volume-title":"Arithmetic circuits: the chasm at depth four gets wider. CoRR, abs\/1006.4700","author":"Koiran P.","year":"2010","unstructured":"P. Koiran . 2010. Arithmetic circuits: the chasm at depth four gets wider. CoRR, abs\/1006.4700 ( 2010 ). P. Koiran. 2010. Arithmetic circuits: the chasm at depth four gets wider. CoRR, abs\/1006.4700 (2010)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a006"},{"key":"e_1_3_2_1_38_1","volume-title":"FOCS","author":"Limaye N.","year":"2021","unstructured":"N. Limaye , S. Srinivasan , and S. Tavenas . 2022. Superpolynomial lower bounds against low-depth algebraic circuits . In FOCS 2021 . N. Limaye, S. Srinivasan, and S. Tavenas. 2022. Superpolynomial lower bounds against low-depth algebraic circuits. In FOCS 2021."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0167-5"},{"volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 259\u2013271","author":"Peleg S.","key":"e_1_3_2_1_40_1","unstructured":"S. Peleg and A. Shpilka . 2021. Polynomial time deterministic identity testing algorithm for \u03a3 ^[3]\u03a0 \u03a3 \u03a0 ^[2] circuits via Edelstein\u2013Kelly type theorem for quadratic polynomials . In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 259\u2013271 . S. Peleg and A. Shpilka. 2021. Polynomial time deterministic identity testing algorithm for \u03a3 ^[3]\u03a0 \u03a3 \u03a0 ^[2] circuits via Edelstein\u2013Kelly type theorem for quadratic polynomials. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 259\u2013271."},{"key":"e_1_3_2_1_41_1","unstructured":"Sh. Peleg A. Shpilka and B. Volk. 2022. Tensor Reconstruction Beyond Constant Rank. Electron. Colloquium Comput. Complex. TR22-125 (2022) ECCC:TR22-125. https:\/\/eccc.weizmann.ac.il\/report\/2022\/125 \t\t\t\t  Sh. Peleg A. Shpilka and B. Volk. 2022. Tensor Reconstruction Beyond Constant Rank. Electron. Colloquium Comput. Complex. TR22-125 (2022) ECCC:TR22-125. https:\/\/eccc.weizmann.ac.il\/report\/2022\/125"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3460-4"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770679"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/10848232"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528403"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0105-8"},{"key":"e_1_3_2_1_48_1","first-page":"3","article-title":"Arithmetic Circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka A.","year":"2010","unstructured":"A. Shpilka and A. Yehudayoff . 2010 . Arithmetic Circuits: A survey of recent results and open questions . Foundations and Trends in Theoretical Computer Science , 5 , 3 - 4 (2010), 207\u2013388. A. Shpilka and A. Yehudayoff. 2010. Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5, 3-4 (2010), 207\u2013388.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.31"},{"key":"e_1_3_2_1_50_1","first-page":"125","article-title":"Efficient reconstruction of depth three circuits with top fan-in two","volume":"27","author":"Sinha G.","year":"2020","unstructured":"G. Sinha . 2020 . Efficient reconstruction of depth three circuits with top fan-in two . Electron. Colloquium Comput. Complex. , 27 (2020), 125 . https:\/\/eccc.weizmann.ac.il\/report\/2020\/125 G. Sinha. 2020. Efficient reconstruction of depth three circuits with top fan-in two. Electron. Colloquium Comput. Complex., 27 (2020), 125. https:\/\/eccc.weizmann.ac.il\/report\/2020\/125","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"S. Tavenas. 2013. Improved Bounds for Reduction to Depth 4 and Depth 3. In MFCS. 813\u2013824. \t\t\t\t  S. Tavenas. 2013. Improved Bounds for Reduction to Depth 4 and Depth 3. In MFCS. 813\u2013824.","DOI":"10.1007\/978-3-642-40313-2_71"},{"key":"e_1_3_2_1_52_1","unstructured":"I. Volkovich. 2015. Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials. In APPROX-RANDOM. 943\u2013958. \t\t\t\t  I. Volkovich. 2015. Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials. In APPROX-RANDOM. 943\u2013958."},{"key":"e_1_3_2_1_53_1","first-page":"1","article-title":"On some Computations on Sparse Polynomials","volume":"48","author":"Volkovich I.","year":"2017","unstructured":"I. Volkovich . 2017 . On some Computations on Sparse Polynomials . In APPROX-RANDOM. 48 : 1 \u2013 4 :21. I. Volkovich. 2017. On some Computations on Sparse Polynomials. In APPROX-RANDOM. 48:1\u20134:21.","journal-title":"APPROX-RANDOM."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585149","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585149","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":54,"alternative-id":["10.1145\/3564246.3585149","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585149","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}