{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:10:46Z","timestamp":1753881046478,"version":"3.41.2"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"abstract":"<jats:p>\n            We present a deterministic algorithm for reconstructing multilinear\n            <jats:italic>\u03a3\u03a0\u03a3\u03a0<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) circuits, i.e. multilinear depth-4 circuits with fan-in\n            <jats:italic>k<\/jats:italic>\n            at the top + gate. For any fixed\n            <jats:italic>k<\/jats:italic>\n            , given black-box access to a polynomial\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJaX\">\\(f \\in \\mathbb {F}[x_{1},x_{2},\\ldots,x_{n} ] \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            computable by a multilinear\n            <jats:italic>\u03a3\u03a0\u03a3\u03a0<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) circuit of size\n            <jats:italic>s<\/jats:italic>\n            , the algorithm runs in time quasi-poly(\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJaX\">\\(n,s,|\\mathbb {F}|) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and outputs a multilinear\n            <jats:italic>\u03a3\u03a0\u03a3\u03a0<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) circuit of size quasi-poly(\n            <jats:italic>n<\/jats:italic>\n            ,\n            <jats:italic>s<\/jats:italic>\n            ) that computes\n            <jats:italic>f<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Our result solves an open problem posed in [GKL12] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear\n            <jats:italic>\u03a3\u03a0\u03a3\u03a0<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) circuits were known only for the case of\n            <jats:italic>k<\/jats:italic>\n            = 2 [GKL12,Vol17].\n          <\/jats:p>","DOI":"10.1145\/3726532","type":"journal-article","created":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:47:20Z","timestamp":1743155240000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Reconstruction of Depth-4 Multilinear Circuits"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-7869-377X","authenticated-orcid":false,"given":"Vishwas","family":"Bhargava","sequence":"first","affiliation":[{"name":"Computing + Mathematical Sciences, California Institute of Technology, Pasadena, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0874-2978","authenticated-orcid":false,"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Department of Computer Science, University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7616-0751","authenticated-orcid":false,"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[{"name":"Computer Science, Boston College, Chestnut Hill, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,3,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"First International Symposium, ANTS-I","author":"Adleman M.","year":"1994","unstructured":"L.\u00a0M. Adleman and K.\u00a0S. McCurley. 1994. Open problems in number theoretic complexity, II. In Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, May 6-9, 1994, Proceedings. 291\u2013322."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 25th FSTTCS(LNCS, Vol.\u00a0 3821)","author":"Agrawal M.","year":"2005","unstructured":"M. Agrawal. 2005. Proving Lower Bounds Via Pseudo-random Generators. In Proceedings of the 25th FSTTCS(LNCS, Vol.\u00a0 3821). 92\u2013105."},{"volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 67\u201375","author":"Agrawal M.","key":"e_1_2_1_3_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."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"e_1_2_1_5_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_2_1_6_1","unstructured":"M. Ben-Or and P. Tiwari. 1988. A Deterministic Algorithm\u00a0for Sparse Multivariate Polynominal Interpolation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC). 301\u2013309."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451096"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1550"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300001157"},{"volume-title":"Proceedings of the 31st Conference on Computational Complexity, CCC. 1\u201324","author":"Carmosino L.","key":"e_1_2_1_11_1","unstructured":"M.\u00a0L. Carmosino, R. Impagliazzo, V. Kabanets, and A. Kolokolova. 2016. Learning Algorithms from Natural Proofs. In Proceedings of the 31st Conference on Computational Complexity, CCC. 1\u201324."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"e_1_2_1_14_1","first-page":"115","article-title":"Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs","volume":"19","author":"Forbes A.","year":"2012","unstructured":"M.\u00a0A. 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_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.006"},{"key":"e_1_2_1_16_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_2_1_17_1","volume-title":"Efficient Reconstruction of Random Multilinear Formulas. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS. 778\u2013787","author":"Gupta A.","year":"2011","unstructured":"A. Gupta, N. Kayal, and S.\u00a0V. Lokam. 2011. Efficient Reconstruction of Random Multilinear Formulas. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS. 778\u2013787."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). 625\u2013642","author":"Gupta A.","year":"2012","unstructured":"A. Gupta, N. Kayal, and S.\u00a0V. 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_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-014-0085-0"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 38th ICALP. 416\u2013423","author":"Harkins C.","year":"2011","unstructured":"R.\u00a0C. Harkins and J.\u00a0M. Hitchcock. 2011. Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. In Proceedings of the 38th ICALP. 416\u2013423."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90014-6"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC). 262\u2013272","author":"Heintz J.","year":"1980","unstructured":"J. Heintz and C.\u00a0P. 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."},{"volume-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC). 355\u2013364","author":"Kabanets V.","key":"e_1_2_1_23_1","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). 355\u2013364."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/110824516"},{"volume-title":"Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC). 274\u2013285","author":"Karnin S.","key":"e_1_2_1_26_1","unstructured":"Z.\u00a0S. 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\/\u00a0shpilka\/publications\/KarninShpilka09.pdf.."},{"key":"e_1_2_1_27_1","first-page":"29","article-title":"Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs","volume":"25","author":"Kayal N.","year":"2018","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), 29. https:\/\/eccc.weizmann.ac.il\/report\/2018\/029","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.21"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316360"},{"key":"e_1_2_1_30_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.."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"e_1_2_1_32_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.","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_2_1_33_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."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.008"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.008"},{"key":"e_1_2_1_36_1","unstructured":"P. Koiran. 2010. Arithmetic circuits: the chasm at depth four gets wider. CoRR abs\/1006.4700(2010)."},{"key":"e_1_2_1_37_1","unstructured":"M. Kumar R. de Oliveira and R. Saptharishi. 2019. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. CoRR abs\/1902.07063(2019). http:\/\/arxiv.org\/abs\/1902.07063"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"D. Minahan and I. Volkovich. 2018. Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. TOCT 10 3 (2018) 10:1\u201310:11. http:\/\/doi.acm.org\/10.1145\/3196836","DOI":"10.1145\/3196836"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2024.87"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970138462X"},{"volume-title":"19th Annual IEEE Conference on Computational Complexity. 215\u2013222","author":"Raz R.","key":"e_1_2_1_41_1","unstructured":"R. Raz and A. Shpilka. 2004. In 19th Annual IEEE Conference on Computational Complexity. 215\u2013222."},{"key":"e_1_2_1_42_1","unstructured":"R. Saptharishi and A. Tengse. 2017. Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees. CoRR abs\/1709.03068(2017). http:\/\/arxiv.org\/abs\/1709.03068"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3460-4"},{"volume-title":"Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC). 137\u2013148","author":"Saxena N.","key":"e_1_2_1_44_1","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). 137\u2013148."},{"volume-title":"Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 21\u201330","author":"Saxena N.","key":"e_1_2_1_45_1","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). 21\u201330."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_47_1","unstructured":"Y. Shitov. 2016. How hard is the tensor rank?arXiv preprint arXiv:1611.01559(2016)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/070694879"},{"key":"e_1_2_1_49_1","volume-title":"37th International Colloquium (ICALP). 408\u2013419","author":"Shpilka A.","year":"2010","unstructured":"A. Shpilka and I. Volkovich. 2010. On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. In Automata, Languages and Programming, 37th International Colloquium (ICALP). 408\u2013419. Full version at https:\/\/eccc.weizmann.ac.il\/report\/2010\/036.."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a018"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0105-8"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.31"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2022.118"},{"key":"e_1_2_1_54_1","unstructured":"M. Sudan. 1998. Algebra and Computation. http:\/\/people.csail.mit.edu\/madhu\/FT98\/course.html. http:\/\/people.csail.mit.edu\/madhu\/FT98\/course.html Lecture notes."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"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_2_1_57_1","volume-title":"Proceedings of the 29th Conference on Learning Theory, (COLT). 1540\u20131561","author":"Volkovich I.","year":"2016","unstructured":"I. Volkovich. 2016. A Guide to Learning Arithmetic Circuits. In Proceedings of the 29th Conference on Learning Theory, (COLT). 1540\u20131561. http:\/\/jmlr.org\/proceedings\/papers\/v49\/volkovich16.html"},{"key":"e_1_2_1_58_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\u20134:21.","journal-title":"APPROX-RANDOM."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3726532","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:49:32Z","timestamp":1743155372000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3726532"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,28]]},"references-count":59,"alternative-id":["10.1145\/3726532"],"URL":"https:\/\/doi.org\/10.1145\/3726532","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,3,28]]},"assertion":[{"value":"2024-06-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3726532"}}