{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:37Z","timestamp":1778498017218,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Collaboration on Algorithms and Geometry"},{"name":"BSF","award":["2014359"],"award-info":[{"award-number":["2014359"]}]},{"name":"Sloan research fellowship"},{"name":"NSF","award":["CCF-1350572, CCF-1540634, CCF-1909683"],"award-info":[{"award-number":["CCF-1350572, CCF-1540634, CCF-1909683"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451096","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"809-822","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits"],"prefix":"10.1145","author":[{"given":"Vishwas","family":"Bhargava","sequence":"first","affiliation":[{"name":"Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[{"name":"Boston College, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"II. In International Algorithmic Number Theory Symposium. Pages 291\u2013322","author":"Adleman L. M.","unstructured":"L. M. Adleman and K. S. McCurley. 1994. Open problems in number theoretic complexity, II. In International Algorithmic Number Theory Symposium. Pages 291\u2013322."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Pages 67\u201375","author":"Agrawal M.","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). Pages 67\u201375."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-4009-0"},{"key":"e_1_3_2_1_5_1","volume-title":"Queries and Concept Learning. Machine Learning, 2","author":"Angluin D.","year":"1988","unstructured":"D. Angluin. 1988. Queries and Concept Learning. Machine Learning, 2, 1988. Pages 319\u2013342."},{"key":"e_1_3_2_1_6_1","first-page":"4","article-title":"2010","volume":"208","author":"Arvind V.","year":"2010","unstructured":"V. Arvind and P. Mukhopadhyay. 2010. The Monomial Ideal Membership Problem and Polynomial Identity Testing. Information and Computation, 208, 4, 2010. Pages 351\u2013363.","journal-title":"Information and Computation"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337257"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC). Pages 301\u2013309","author":"Ben-Or M.","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). Pages 301\u2013309."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.132"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-33275-6_15"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.10"},{"key":"e_1_3_2_1_13_1","first-page":"1227","volume-title":"Learning Polynomials in Few Relevant Dimensions. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. 125","author":"Chen S.","year":"2020","unstructured":"S. Chen, R. Meka, Jacob D. Abernethy, and Shivani Agarwal. 2020. Learning Polynomials in Few Relevant Dimensions. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. 125, PMLR. Pages 1161\u20131227. http:\/\/proceedings.mlr.press\/v125\/chen20a.html"},{"key":"e_1_3_2_1_14_1","volume-title":"varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra (4. ed.)","author":"Cox D. A.","unstructured":"D. A. Cox, J. Little, and D. O'Shea. 2015. Ideals, varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra (4. ed.). Springer."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591816"},{"key":"e_1_3_2_1_17_1","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. Pages 115."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.006"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"A. Garg N. Kayal and C. Saha. 2020. Learning sums of powers of low-degree polynomials in the non-degenerate case. arXiv preprint arXiv:2004.06898 2020.","DOI":"10.1109\/FOCS46700.2020.00087"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80005-1"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.68"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.70"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). Pages 625\u2013642","author":"Gupta A.","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). Pages 625\u2013642."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-014-0085-0"},{"key":"e_1_3_2_1_25_1","first-page":"4","article-title":"1990. Tensor Rank is NP-Complete","volume":"11","author":"Johan","year":"1990","unstructured":"Johan H\\r astad. 1990. Tensor Rank is NP-Complete. J. Algorithms, 11, 4, 1990. Pages 644\u2013654.","journal-title":"J. Algorithms"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"M. D. Huang and Y. C. Wong. 1999. Solvability of systems of polynomial congruences modulo a large prime. computational complexity 8 3 1999. Pages 227\u2013257.","DOI":"10.1007\/s000370050029"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73020"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC). Pages 355\u2013364","author":"Kabanets V.","unstructured":"V. Kabanets and R. Impagliazzo. 2003. Derandomizing polynomial identity tests means proving circuit lower bounds. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC). Pages 355\u2013364."},{"key":"e_1_3_2_1_29_1","first-page":"3","article-title":"1990. Computing with Polynomials Given by Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization","volume":"9","author":"Kaltofen E.","year":"1990","unstructured":"E. Kaltofen and B. M. Trager. 1990. Computing with Polynomials Given by Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators. J. of Symbolic Computation, 9, 3, 1990. Pages 301\u2013320.","journal-title":"Separation of Numerators and Denominators. J. of Symbolic Computation"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC). Pages 274\u2013285","author":"Karnin Z. S.","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). Pages 274\u2013285."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2537-3"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.108"},{"key":"e_1_3_2_1_33_1","unstructured":"N. Kayal V. Nair and C. Saha. 2018. Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 25 2018. Pages 29. https:\/\/eccc.weizmann.ac.il\/report\/2018\/029"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.21"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316360"},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Pages 198\u2013207","author":"Kayal N.","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). Pages 198\u2013207."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"A. Klivans and A. Shpilka. 2006. Learning restricted models of arithmetic circuits.. Theory of computing 2 10 2006. Pages 185\u2013206.","DOI":"10.4086\/toc.2006.v002a010"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). Pages 216\u2013223","author":"Klivans A.","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). Pages 216\u2013223."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.008"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/868026"},{"key":"e_1_3_2_1_42_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."},{"key":"e_1_3_2_1_43_1","volume-title":"Tensors: geometry and applications. Representation theory, 381, 402","author":"Landsberg J.","year":"2012","unstructured":"J. Landsberg. 2012. Tensors: geometry and applications. Representation theory, 381, 402, 2012. Pages 3."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-27-1-521-553"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535928"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC). Pages 137\u2013148","author":"Saxena N.","unstructured":"N. Saxena and C. Seshadhri. 2009. An Almost Optimal Rank Bound for Depth-3 Identities. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC). Pages 137\u2013148."},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS). Pages 21\u201330","author":"Saxena N.","unstructured":"N. Saxena and C. Seshadhri. 2010. From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Deph-3 Circuits. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS). Pages 21\u201330."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770679"},{"key":"e_1_3_2_1_49_1","first-page":"5","article-title":"2012. Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits","volume":"41","author":"Saxena N.","year":"2012","unstructured":"N. Saxena and C. Seshadhri. 2012. Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter. SIAM J. Comput., 41, 5, 2012. Pages 1285\u20131298.","journal-title":"The Field Doesn't Matter. SIAM J. Comput."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528403"},{"key":"e_1_3_2_1_51_1","unstructured":"M. Schaefer and D. Stefankovic. 2016. The Complexity of Tensor Rank. CoRR abs\/1612.04338 2016. arxiv:1612.04338"},{"key":"e_1_3_2_1_52_1","volume-title":"How hard is the tensor rank? arXiv preprint arXiv:1611.01559","author":"Shitov Y.","year":"2016","unstructured":"Y. Shitov. 2016. How hard is the tensor rank? arXiv preprint arXiv:1611.01559, 2016."},{"key":"e_1_3_2_1_53_1","series-title":"SIAM J. on Computing, 38, 6","volume-title":"Interpolation of depth-3 arithmetic circuits with two multiplication gates","author":"Shpilka A.","year":"2009","unstructured":"A. Shpilka. 2009. Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J. on Computing, 38, 6, 2009. Pages 2130\u20132161."},{"key":"e_1_3_2_1_54_1","first-page":"3","article-title":"2015","volume":"24","author":"Shpilka A.","year":"2015","unstructured":"A. Shpilka and I. Volkovich. 2015. Read-Once Polynomial Identity Testing. Computational Complexity, 24, 3, 2015. Pages 477\u2013532.","journal-title":"Read-Once Polynomial Identity Testing. Computational Complexity"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.31"},{"key":"e_1_3_2_1_56_1","volume-title":"Efficient reconstruction of depth three circuits with top fan-in two. Electron. Colloquium Comput. Complex., 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. Pages 125. https:\/\/eccc.weizmann.ac.il\/report\/2020\/125"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"crossref","unstructured":"S. Tavenas. 2013. Improved Bounds for Reduction to Depth 4 and Depth 3. In MFCS. Pages 813\u2013824.","DOI":"10.1007\/978-3-642-40313-2_71"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451096","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451096","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":57,"alternative-id":["10.1145\/3406325.3451096","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451096","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}