{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:45Z","timestamp":1781078265343,"version":"3.54.1"},"reference-count":111,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,6,11]],"date-time":"2022-06-11T00:00:00Z","timestamp":1654905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"Newton iteration is an almost 350-year-old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all roots simultaneously. In this form, the process yields better circuit complexity in the case when the number of rootsr<\/jats:italic>is small but the multiplicities are exponentially large. Our method sets up a linear system inr<\/jats:italic>unknowns and iteratively builds the roots as formal power series. For an algebraic circuit\\( f(x_1,\\ldots ,x_n) \\)<\/jats:tex-math><\/jats:inline-formula>of sizes<\/jats:italic>, we prove that each factor has size at most a polynomial ins<\/jats:italic>and the degree of the squarefree part off<\/jats:italic>. Consequently, if\\( f_1 \\)<\/jats:tex-math><\/jats:inline-formula>is a\\( 2^{\\Omega (n)} \\)<\/jats:tex-math><\/jats:inline-formula>-hard polynomial, then any nonzero multiple\\( \\prod _{i} f_i^{e_i} \\)<\/jats:tex-math><\/jats:inline-formula>is equally hard for arbitrary positive\\( e_i \\)<\/jats:tex-math><\/jats:inline-formula>\u2019s, assuming that\\( \\sum _i\\deg (f_i) \\)<\/jats:tex-math><\/jats:inline-formula>is at most\\( 2^{O(n)} \\)<\/jats:tex-math><\/jats:inline-formula>.<\/jats:p>It is an old open question whether the class of poly(n<\/jats:italic>) size formulas (respectively, algebraic branching programs) is closed under factoring. We show that given a polynomialf<\/jats:italic>of degree\\( n^{O(1)} \\)<\/jats:tex-math><\/jats:inline-formula>and formula (respectively, algebraic branching program) size\\( n^{O(\\log n)} \\)<\/jats:tex-math><\/jats:inline-formula>, we can find a similar-size formula (respectively, algebraic branching program) factor in randomized poly(\\( n^{\\log n} \\)<\/jats:tex-math><\/jats:inline-formula>) time. Consequently, if the determinant requires an\\( n^{\\Omega (\\log n)} \\)<\/jats:tex-math><\/jats:inline-formula>size formula, then the same can be said about any of its nonzero multiples.<\/jats:p>In all of our proofs, we exploit the following property of multivariate polynomial factorization. Under a random linear transformation\\( \\tau \\)<\/jats:tex-math><\/jats:inline-formula>, the polynomial\\( f(\\tau \\overline{x}) \\)<\/jats:tex-math><\/jats:inline-formula>completely factors via power series roots. Moreover, the factorization adapts well to circuit complexity analysis. Therefore, with the help of the strong mathematical characterizations and the \u2018allRootsNI\u2019 technique, we make significant progress towards the old open problems; supplementing the vast body of classical results and concepts in algebraic circuit factorization (e.g., [17<\/jats:xref>,51<\/jats:xref>,54<\/jats:xref>,111<\/jats:xref>]).<\/jats:p>","DOI":"10.1145\/3510359","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T21:57:36Z","timestamp":1645653456000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9137-9025","authenticated-orcid":false,"given":"Pranjal","family":"Dutta","sequence":"first","affiliation":[{"name":"Chennai Mathematical Institute"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Kanpur"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amit","family":"Sinhababu","sequence":"additional","affiliation":[{"name":"Aalen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1973-0329236-7"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1901272116"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_3_3_5_2","article-title":"Multivariate power series in Maple","author":"Asadi Mohammadali","year":"2021","unstructured":"Mohammadali Asadi, Alexander Brandt, Mahsa Kazemi, Marc Moreno Maza, and Erik Postma. 2021. Multivariate power series in Maple. arXiv preprint arXiv:2106.15519 (2021).","journal-title":"arXiv preprint arXiv:2106.15519"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.887868"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221006"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00088"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"e_1_3_3_10_2"},{"key":"e_1_3_3_11_2","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919)","author":"Bl\u00e4ser Markus","year":"2018","unstructured":"Markus Bl\u00e4ser and Gorav Jindal. 2018. On the complexity of symmetric polynomials. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919)."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_3_3_14_2","volume-title":"Algebra II: Chapters 4-7","author":"Bourbaki Nicolas","year":"2013","unstructured":"Nicolas Bourbaki. 2013. Algebra II: Chapters 4-7. Elements of Mathematics. Springer Science & Business Media."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322099"},{"key":"e_1_3_3_16_2"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44683-4_2"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/3115473.3115783"},{"key":"e_1_3_3_19_2","volume-title":"Completeness and Reduction in Algebraic Complexity Theory","author":"B\u00fcrgisser Peter","year":"2013","unstructured":"Peter B\u00fcrgisser. 2013. Completeness and Reduction in Algebraic Complexity Theory, Vol. 7. Springer Science & Business Media."},{"key":"e_1_3_3_20_2","volume-title":"Algebraic Complexity Theory","author":"B\u00fcrgisser Peter","year":"2013","unstructured":"Peter B\u00fcrgisser, Michael Clausen, and Amin Shokrollahi. 2013. Algebraic Complexity Theory, Vol. 315. Springer Science & Business Media."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/10722028_10"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1981-0606517-5"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02112431"},{"key":"e_1_3_3_24_2","article-title":"Closure of VP under taking factors: A short and simple proof","author":"Chou Chi-Ning","year":"2019","unstructured":"Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. 2019. Closure of VP under taking factors: A short and simple proof. arXiv preprint arXiv:1903.02366 (2019).","journal-title":"arXiv preprint arXiv:1903.02366"},{"key":"e_1_3_3_25_2"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195105193.001.0001","volume-title":"What Is Mathematics? An Elementary Approach to Ideas and Methods","author":"Courant Richard","year":"1996","unstructured":"Richard Courant, Herbert Robbins, and Ian Stewart. 1996. What Is Mathematics? An Elementary Approach to Ideas and Methods. Oxford University Press."},{"key":"e_1_3_3_27_2","article-title":"Numerical Methods in Scientific Computin g, Vol. I","author":"Dahlquist Germund","year":"2008","unstructured":"Germund Dahlquist and \u00c5ke Bj\u00f6rck. 2008. Numerical Methods in Scientific Computing, Vol. I. Society for Industrial and Applied Mathematics.","journal-title":"Society for Industrial and Applied Mathematics."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_3_29_2","first-page":"279","volume-title":"Racines d\u2019une Polyn\u00f4me","author":"Durand \u00c9mile","year":"1960","unstructured":"\u00c9mile Durand. 1960. Solutions num\u00e9riques des \u00e9quations alg\u00e9briques. Tome I, \u00c9quations du type F(x)= 0. In Racines d\u2019une Polyn\u00f4me. Masson, 279\u2013281."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79416-3_5"},{"key":"e_1_3_3_31_2","volume-title":"Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS\u201921)","author":"Dutta Pranjal","year":"2021","unstructured":"Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. 2021. Demystifying the border of depth-3 algebraic circuits. In Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS\u201921)."},{"key":"e_1_3_3_32_2"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.25"},{"key":"e_1_3_3_34_2","volume-title":"Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS\u201921)","author":"Dutta Pranjal","year":"2021","unstructured":"Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. 2021. A largish sum-of-squares implies circuit hardness and derandomization. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS\u201921)."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1957999"},{"key":"e_1_3_3_36_2","article-title":"Efficiently factoring polynomials modulo \\( p^4 \\)","author":"Dwivedi Ashish","year":"2019","unstructured":"Ashish Dwivedi, Rajat Mittal, and Nitin Saxena. 2019. Efficiently factoring polynomials modulo \\( p^4 \\) . arxiv preprint arXiv:1901.06628 (2019).","journal-title":"arxiv preprint arXiv:1901.06628"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/363067.363115"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2852040.2852051"},{"key":"e_1_3_3_39_2","first-page":"32","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC\u201916)","author":"Forbes Michael A.","year":"2016","unstructured":"Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. 2016. Proof complexity lower bounds from algebraic circuit complexity. In Proceedings of the 31st Conference on Computational Complexity (CCC\u201916). 32."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/763377.763392"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80040-3"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(96)00099-0"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2015.11.013"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0103-x"},{"issue":"130","key":"e_1_3_3_45_2","article-title":"Complexity in ideals of polynomials: Questions on algebraic complexity of circuits and proofs","volume":"1","author":"Grochow Joshua A.","year":"2020","unstructured":"Joshua A. Grochow. 2020. Complexity in ideals of polynomials: Questions on algebraic complexity of circuits and proofs. Bulletin of EATCS 1, 130 (2020), 24 pages.","journal-title":"Bulletin of EATCS"},{"key":"e_1_3_3_46_2","first-page":"Article 34, 14","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u20196)","volume":"55","author":"Grochow Joshua A.","year":"2016","unstructured":"Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. 2016. Boundaries of VP and VNP. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u20196), Vol. 55. Article 34, 14 pages."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743426"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02505-6"},{"key":"e_1_3_3_49_2","first-page":"87","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS\u201911)","author":"Jansen Maurice J.","year":"2011","unstructured":"Maurice J. Jansen. 2011. Extracting roots of arithmetic circuits by adapting numerical methods. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS\u201911). 87\u2013100. http:\/\/homepages.inf.ed.ac.uk\/mjansen1\/Jansen10.pdf."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780595"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22160"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214035"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12163"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28443"},{"key":"e_1_3_3_55_2","first-page":"375","article-title":"Factorization of polynomials given by straight-line programs","volume":"5","author":"Kaltofen Erich","year":"1989","unstructured":"Erich Kaltofen. 1989. Factorization of polynomials given by straight-line programs. Randomness and Computation 5 (1989), 375\u2013412.","journal-title":"Randomness and Computation"},{"key":"e_1_3_3_56_2","unstructured":"Erich Kaltofen. 1990. Polynomial factorization 1982\u20131986. In Computers in Mathematics . CRC Press Boca Raton FL 86\u2013111."},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023837"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/1390768.1390790"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.18"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.108"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0219-8"},{"key":"e_1_3_3_62_2","volume-title":"A Course in Commutative Algebra","author":"Kemper Gregor","year":"2010","unstructured":"Gregor Kemper. 2010. A Course in Commutative Algebra, Vol. 256. Springer Science & Business Media."},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02162564"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0102-y"},{"key":"e_1_3_3_65_2","volume-title":"The Implicit Function Theorem: History, Theory, and Applications","author":"Krantz Steven G.","year":"2012","unstructured":"Steven G. Krantz and Harold R. Parks. 2012. The Implicit Function Theorem: History, Theory, and Applications. Springer Science & Business Media."},{"key":"e_1_3_3_66_2","first-page":"96","article-title":"Straight-line programs in polynomial equation solving","volume":"312","author":"Krick Teresa","year":"2002","unstructured":"Teresa Krick. 2002. Straight-line programs in polynomial equation solving. Foundations of Computational Mathematics: Minneapolis 312 (2002), 96\u2013136.","journal-title":"Foundations of Computational Mathematics: Minneapolis"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.40"},{"key":"e_1_3_3_68_2","first-page":"Article 34, 27","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC\u201916)","author":"Kumar Mrinal","year":"2016","unstructured":"Mrinal Kumar and Shubhangi Saraf. 2016. Arithmetic circuits with locally low algebraic rank. In Proceedings of the 31st Conference on Computational Complexity (CCC\u201916). Article 34, 27 pages."},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/322063.322068"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214015"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1007\/s102080010026"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.5555\/646657.700265"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100295"},{"key":"e_1_3_3_75_2","volume-title":"Finite Fields","author":"Lidl Rudolph","year":"1997","unstructured":"Rudolph Lidl and Harald Niederreiter. 1997. Finite Fields. Cambridge University Press, Cambridge, UK."},{"key":"e_1_3_3_76_2","first-page":"81","article-title":"Superpolynomial lower bounds against low-depth algebraic circuits","volume":"28","author":"Limaye Nutan","year":"2021","unstructured":"Nutan Limaye, Srikanth Srinivasan, and S\u00e9bastien Tavenas. 2021. Superpolynomial lower bounds against low-depth algebraic circuits. Electronic Colloquium on Computational Complexity 28 (2021), 81. https:\/\/eccc.weizmann.ac.il\/report\/2021\/081.","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90041-7"},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.83"},{"key":"e_1_3_3_79_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05446-9_4"},{"key":"e_1_3_3_80_2","first-page":"730","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997)","author":"Mahajan Meena","year":"1997","unstructured":"Meena Mahajan and V. Vinay. 1997. A combinatorial algorithm for the determinant. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997). 730\u2013738."},{"key":"e_1_3_3_81_2","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/864"},{"key":"e_1_3_3_82_2","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184341"},{"key":"e_1_3_3_83_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.15"},{"key":"e_1_3_3_84_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087642"},{"key":"e_1_3_3_85_2","unstructured":"Isaac Newton. 1669. De Analysi per aequationes numero terminorum infinitas [On analysis by infinite series] (in Latin). Published in 1711 by William Jones."},{"key":"e_1_3_3_86_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0130-2"},{"issue":"7","key":"e_1_3_3_87_2","first-page":"15","article-title":"\u00dcber h\u00f6here kongruenzen","volume":"1","author":"Ore Oystein","year":"1922","unstructured":"Oystein Ore. 1922. \u00dcber h\u00f6here kongruenzen. Norsk Matematisk Forenings Skrifter 1, 7 (1922), 15.","journal-title":"Norsk Matematisk Forenings Skrifter"},{"key":"e_1_3_3_88_2","volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916)","author":"Pandey Anurag","year":"2016","unstructured":"Anurag Pandey, Nitin Saxena, and Amit Sinhababu. 2016. Algebraic independence over positive characteristic: New criterion and applications to locally low algebraic rank circuits. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916). Article 74, 15 pages."},{"key":"e_1_3_3_89_2","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2001.0493"},{"key":"e_1_3_3_90_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80013-5"},{"key":"e_1_3_3_91_2","unstructured":"Ramprasad Saptharishi. 2019. A Survey of Lower Bounds in Arithmetic Circuit Complexity. Retrieved March 2 2022 from https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases."},{"key":"e_1_3_3_92_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167201"},{"key":"e_1_3_3_93_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_133"},{"key":"e_1_3_3_94_2","article-title":"The fundamental theorem of algebra in terms of computational complexity","author":"Sch\u00f6nhage Arnold","year":"1982","unstructured":"Arnold Sch\u00f6nhage. 1982. The fundamental theorem of algebra in terms of computational complexity. Manuscript. University of T\u00fcbingen, Germany.","journal-title":"Manuscript. University of T\u00fcbingen, Germany."},{"key":"e_1_3_3_95_2","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_3_96_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_3_97_2","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982476"},{"key":"e_1_3_3_98_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.33"},{"key":"e_1_3_3_99_2","first-page":"184","article-title":"Vermeidung von divisionen.","volume":"264","author":"Strassen Volker","year":"1973","unstructured":"Volker Strassen. 1973. Vermeidung von divisionen. Journal f\u00fcr Die Reine Und Angewandte Mathematik 264 (1973), 184\u2013202.","journal-title":"Journal f\u00fcr Die Reine Und Angewandte Mathematik"},{"key":"e_1_3_3_100_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_3_101_2","unstructured":"Brook Taylor. 1715. Methodus incrementorum directa et inversa [Direct and reverse methods of incrementation] (in Latin). Translated into English in Struik D. J. 1969. A Source Book in Mathematics 1200\u20131800 . Harvard University Press Cambridge MA 329\u2013332."},{"key":"e_1_3_3_102_2","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_3_103_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_3_3_104_2","unstructured":"Ming Li and Paul M. B. Vitanyi. 1997. An Introduction to Kolmogorov Complexity and Its Applications . Texts in Computer Science. Springer."},{"key":"e_1_3_3_105_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1984-0736459-9"},{"key":"e_1_3_3_106_2","doi-asserted-by":"publisher","DOI":"10.5555\/2512973"},{"key":"e_1_3_3_107_2","volume-title":"Factorization of Polynomials Modulo Small Prime Powers","author":"Gathen Joachim von zur","year":"1996","unstructured":"Joachim von zur Gathen and Silke Hartlieb. 1996. Factorization of Polynomials Modulo Small Prime Powers. Univ.-Gesamthochsch.-Paderborn, Fachbereich Mathematik-Informatik."},{"key":"e_1_3_3_108_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90044-3"},{"key":"e_1_3_3_109_2","unstructured":"Wikipedia. n.d. Cauchy Matrix. Retrieved March 2 2022 from https:\/\/en.wikipedia.org\/wiki\/Cauchy_matrix."},{"key":"e_1_3_3_110_2","unstructured":"Oscar Zariski and Pierre Samuel. 1975. Commutative Algebra: Volume II . Graduate Texts in Mathematics Vol. 29. Springer."},{"key":"e_1_3_3_111_2","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"},{"key":"e_1_3_3_112_2","doi-asserted-by":"crossref","unstructured":"Hans Zassenhaus. 1969. On Hensel factorization I. Journal of Number Theory . Elsevier 1 3 (1969) 291\u2013311.","DOI":"10.1016\/0022-314X(69)90047-X"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3510359","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3510359","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:44Z","timestamp":1750183784000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3510359"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,11]]},"references-count":111,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3510359"],"URL":"https:\/\/doi.org\/10.1145\/3510359","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,11]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}