{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T16:53:23Z","timestamp":1773420803397,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>\n                    We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    computed by a constant-depth circuit over rational numbers, and outputs a list\n                    <jats:italic toggle=\"yes\">L<\/jats:italic>\n                    of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    computable by constant-depth circuits. This list\n                    <jats:italic toggle=\"yes\">L<\/jats:italic>\n                    might also include circuits that are spurious: they either do not correspond to factors of\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    or are not even well-defined, e.g., the input to a division gate is a sub-circuit that computes the identically zero polynomial.\n                  <\/jats:p>\n                  <jats:p>\n                    The key technical ingredient of our algorithm is a notion of the\n                    <jats:italic toggle=\"yes\">pseudo-resultant<\/jats:italic>\n                    of\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    and a factor\n                    <jats:italic toggle=\"yes\">g<\/jats:italic>\n                    , which serves as a proxy for the resultant of\n                    <jats:italic toggle=\"yes\">g<\/jats:italic>\n                    and\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(f\/g\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , with the advantage that the circuit complexity of the pseudo-resultant is comparable to that of the circuit complexity of\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">g<\/jats:italic>\n                    . This notion, which might be of independent interest, together with the recent results of Limaye, Srinivasan, and Tavenas [\n                    <jats:xref ref-type=\"bibr\">19<\/jats:xref>\n                    ] helps us derandomize one key step of multivariate polynomial factorization algorithms \u2014 that of deterministically finding a good starting point for Newton Iteration for the case when the input polynomial as well as the irreducible factor of interest have small constant-depth circuits.\n                  <\/jats:p>","DOI":"10.1145\/3778245","type":"journal-article","created":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T12:04:52Z","timestamp":1764072292000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6430-0219","authenticated-orcid":false,"given":"Mrinal","family":"Kumar","sequence":"first","affiliation":[{"name":"School of Technology and Computer Science, Tata Institute of Fundamental Research","place":["Mumbai, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5903-593X","authenticated-orcid":false,"given":"Varun","family":"Ramanathan","sequence":"additional","affiliation":[{"name":"School of Technology and Computer Science, Tata Institute of Fundamental Research","place":["Mumbai, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7485-3220","authenticated-orcid":false,"given":"Ramprasad","family":"Saptharishi","sequence":"additional","affiliation":[{"name":"School of Technology and Computer Science, Tata Institute of Fundamental Research","place":["Mumbai, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7143-7280","authenticated-orcid":false,"given":"Ben Lee","family":"Volk","sequence":"additional","affiliation":[{"name":"Reichman University","place":["Herzliya, Israel"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,25]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Robert Andrews and Avi Wigderson. 2024. Constant-depth arithmetic circuits for linear algebra problems. arxiv:cs.CC\/2404.10839. Retrieved from https:\/\/arxiv.org\/abs\/2404.10839"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","unstructured":"Vishwas Bhargava Shubhangi Saraf and Ilya Volkovich. 2020. Deterministic factorization of sparse polynomials with bounded individual degree. J. ACM 67 2 (2020) 8:1\u20138:28. DOI:10.1145\/3365667","DOI":"10.1145\/3365667"},{"key":"e_1_3_3_4_2","unstructured":"Somnath Bhattacharjee Mrinal Kumar Shanthanu Rai Varun Ramanathan Ramprasad Saptharishi and Shubhangi Saraf. 2025. Constant-depth circuits for polynomial GCD over any characteristic. arxiv:cs.CC\/2506.23220. Retrieved from https:\/\/arxiv.org\/abs\/2506.23220"},{"key":"e_1_3_3_5_2","unstructured":"Somnath Bhattacharjee Mrinal Kumar Shanthanu S. Rai Varun Ramanathan Ramprasad Saptharishi and Shubhangi Saraf. 2025. Closure under factorization from a result of Furstenberg. arxiv:cs.CC\/2506.23214. Retrieved from https:\/\/arxiv.org\/abs\/2506.23214"},{"key":"e_1_3_3_6_2","unstructured":"Somnath Bhattacharjee Mrinal Kumar Varun Ramanathan Ramprasad Saptharishi and Shubhangi Saraf. 2025. Deterministic factorization of constant-depth algebraic circuits in subexponential time. arxiv:cs.CC\/2504.08063. Retrieved from https:\/\/arxiv.org\/abs\/2504.08063"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04179-6"},{"key":"e_1_3_3_8_2","first-page":"75","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2024)","author":"Dutta Pranjal","year":"2024","unstructured":"Pranjal Dutta, Amit Sinhababu, and Thomas Thierauf. 2024. Derandomizing multivariate polynomial factoring for low degree factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2024). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 75\u20131."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","unstructured":"Zeev Dvir Amir Shpilka and Amir Yehudayoff. 2009. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput. 39 4 (2009) 1279\u20131293. DOI:10.1137\/080735850","DOI":"10.1137\/080735850"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.35"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","unstructured":"Michael A. Forbes and Amir Shpilka. 2015. Complexity theory column 88: Challenges in polynomial factorization1. SIGACT News 46 4 (Dec2015) 32\u201349. DOI:10.1145\/2852040.2852051","DOI":"10.1145\/2852040.2852051"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami and Madhu Sudan. 1999. Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inf. Theor. 45 6 (1999) 1757\u20131767.","DOI":"10.1109\/18.782097"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","unstructured":"Valentine Kabanets and Russell Impagliazzo. 2004. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13 1-2 (2004) 1\u201346. DOI:10.1007\/s00037-004-0182-635th Annual ACM Symposium on Theory of Computing (STOC 2003).","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_3_14_2","first-page":"375","volume-title":"Randomness and Computation","author":"Kaltofen Erich","year":"1989","unstructured":"Erich Kaltofen. 1989. Factorization of polynomials given by straight-line programs. In Randomness and Computation, Silvio Micali and Franco P. Preparata (Eds.). JAI Press, 375\u2013412. Retrieved from https:\/\/users.cs.duke.edu\/elk27\/bibliography\/89\/Ka89_slpfac.pdf"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21946"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591847"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","unstructured":"Swastik Kopparty Shubhangi Saraf and Amir Shpilka. 2015. Equivalence of polynomial identity testing and polynomial factorization. Preliminary Version in the 29th Annual IEEE Conference on Computational Complexity (CCC\u201914) 24 2 (2015) 295\u2013331. DOI:10.1007\/s00037-015-0102-y","DOI":"10.1007\/s00037-015-0102-y"},{"key":"e_1_3_3_18_2","unstructured":"Mrinal Kumar Varun Ramanathan and Ramprasad Saptharishi. 2023. Deterministic algorithms for low degree factors of constant depth circuits. arXiv:2309.09701. Retrieved from https:\/\/arxiv.org\/abs\/2309.09701"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","unstructured":"Arjen K. Lenstra Hendrik W. Lenstra Jr. and L\u00e1szl\u00f3 Lov\u00e1sz. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261 4 (1982) 515\u2013534. DOI:10.1007\/BF01457454","DOI":"10.1007\/BF01457454"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00083"},{"key":"e_1_3_3_21_2","unstructured":"Ramprasad Saptharishi. 2015. A survey of lower bounds in arithmetic circuit complexity. (2015). Retrieved from https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/Github survey."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_35"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","unstructured":"Amit Sinhababu and Thomas Thierauf. 2021. Factorization of polynomials given by arithmetic branching programs. Comput. Complex. 30 2 (2021) 15. DOI:10.1007\/S00037-021-00215-0","DOI":"10.1007\/S00037-021-00215-0"},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","unstructured":"Madhu Sudan. 1997. Decoding of Reed Solomon codes beyond the error-correction bound. J. Complexity 13 1 (1997) 180\u2013193.","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3778245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T15:02:05Z","timestamp":1773414125000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3778245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,25]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3778245"],"URL":"https:\/\/doi.org\/10.1145\/3778245","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,25]]},"assertion":[{"value":"2024-08-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}