{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T15:06:29Z","timestamp":1778166389088,"version":"3.51.4"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,12,1]],"date-time":"2015-12-01T00:00:00Z","timestamp":1448928000000},"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":["SIGACT News"],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p>\n            Algebraic complexity theory studies the complexity of computing (multivariate) polynomials efficiently using algebraic circuits. This succinct representation leads to fundamental algorithmic challenges such as the\n            <jats:italic>polynomial identity testing (PIT)<\/jats:italic>\n            problem (decide nonzeroness of the computed polynomial) and the\n            <jats:italic>polynomial factorization problem<\/jats:italic>\n            (compute succinct representations of the factors of the circuit). While the Schwartz-Zippel-DeMillo-Lipton Lemma [Sch80,Zip79,DL78] gives an easy randomized algorithm for PIT, randomized algorithms for factorization require more ideas as given by Kaltofen [Kal89]. However, even derandomizing PIT remains a fundamental problem in understanding the power of randomness.\n          <\/jats:p>\n          <jats:p>\n            In this column, we survey the factorization problem, discussing the algorithmic ideas as well as the applications to other problems. We then discuss the challenges ahead, in particular focusing on the goal of obtaining deterministic factoring algorithms. While deterministic PIT algorithms have been developed for various restricted circuit classes, there are very few corresponding factoring algorithms. We discuss some recent progress on the\n            <jats:italic>divisibility testing<\/jats:italic>\n            problem (test if a given polynomial divides another given polynomial) which captures some of the difficulty of factoring. Along the way we attempt to highlight key challenges whose solutions we hope will drive progress in the area.\n          <\/jats:p>","DOI":"10.1145\/2852040.2852051","type":"journal-article","created":{"date-parts":[[2015,12,4]],"date-time":"2015-12-04T13:43:07Z","timestamp":1449236587000},"page":"32-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Complexity Theory Column 88"],"prefix":"10.1145","volume":"46","author":[{"given":"Michael A.","family":"Forbes","sequence":"first","affiliation":[{"name":"Princeton University"}]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2015,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975103"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488649"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214033"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62241"},{"key":"e_1_2_1_6_1","volume-title":"varieties, and algorithms. Undergraduate Texts in Mathematics","author":"Cox David","year":"2007","unstructured":"David Cox , John Little , and Donal O'Shea . Ideals , varieties, and algorithms. Undergraduate Texts in Mathematics . Springer , New York , third edition, 2007 . An introduction to computational algebraic geometry and commutative algebra. David Cox, John Little, and Donal O'Shea. Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, New York, third edition, 2007. An introduction to computational algebraic geometry and commutative algebra."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_35"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735850"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.35"},{"key":"e_1_2_1_12_1","first-page":"527","volume-title":"Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM 2013","author":"Michael","year":"2013","unstructured":"Michael A. Forbes and Amir Shpilka. Explicit Noether Normalization for simultaneous conjugation via polynomial identity testing . In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM 2013 ), pages 527 -- 542 , 2013 . Full version at arXiv:1303.0084. Michael A. Forbes and Amir Shpilka. Explicit Noether Normalization for simultaneous conjugation via polynomial identity testing. In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM 2013), pages 527--542, 2013. Full version at arXiv:1303.0084."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.34"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591816"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629541"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833243"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28443"},{"key":"e_1_2_1_19_1","series-title":"Advances in Computing Research","first-page":"375","volume-title":"Randomness and Computation","author":"Kaltofen Erich L.","year":"1989","unstructured":"Erich L. Kaltofen . Factorization of polynomials given by straight-line programs . In Silvio Micali, editor, Randomness and Computation , volume 5 of Advances in Computing Research , pages 375 -- 412 . JAI Press, Inc. , Greenwich, CT, USA , 1989 . Erich L. Kaltofen. Factorization of polynomials given by straight-line programs. In Silvio Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 375--412. JAI Press, Inc., Greenwich, CT, USA, 1989."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1023"},{"key":"e_1_2_1_21_1","volume-title":"An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19(81)","author":"Kayal Neeraj","year":"2012","unstructured":"Neeraj Kayal . An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19(81) , 2012 . Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19(81), 2012."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780595"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380801"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.46"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0102-y"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"e_1_2_1_27_1","volume-title":"Personal Communication","author":"Kumar Mrinal","year":"2015","unstructured":"Mrinal Kumar . Personal Communication , 2015 . Mrinal Kumar. Personal Communication, 2015."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08783-2_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833237"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80013-5"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"e_1_2_1_38_1","volume-title":"A survey of known lower bounds for arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey","author":"Saptharishi Ramprasad","year":"2015","unstructured":"Ramprasad Saptharishi . A survey of known lower bounds for arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey , 2015 . Ramprasad Saptharishi. A survey of known lower bounds for arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey, 2015."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_6"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_41_1","volume-title":"Personal Communication","author":"Saptharishi Ramprasad","year":"2014","unstructured":"Ramprasad Saptharishi and Amir Shpilka . Personal Communication , 2014 . Ramprasad Saptharishi and Amir Shpilka. Personal Communication, 2014."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0054-4"},{"key":"e_1_2_1_43_1","first-page":"184","volume":"264","author":"Strassen Volker","year":"1973","unstructured":"Volker Strassen . Vermeidung von divisionen . J. Reine Angew. Math. , 264 : 184 -- 202 , 1973 . Volker Strassen. Vermeidung von divisionen. J. Reine Angew. Math., 264:184--202, 1973.","journal-title":"J. Reine Angew. Math."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_2_1_45_1","unstructured":"Madhu Sudan. Algebra and computation -- lecture notes. http:\/\/people.csail.mit.edu\/madhu\/FT98\/course.html 1998.  Madhu Sudan. Algebra and computation -- lecture notes. http:\/\/people.csail.mit.edu\/madhu\/FT98\/course.html 1998."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880964"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001609"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786445108645733"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804412"},{"key":"e_1_2_1_52_1","volume-title":"Computations beyond exponentiation gates and applications. Electronic Colloquium on Computational Complexity (ECCC), 22:42","author":"Volkovich Ilya","year":"2015","unstructured":"Ilya Volkovich . Computations beyond exponentiation gates and applications. Electronic Colloquium on Computational Complexity (ECCC), 22:42 , 2015 . Ilya Volkovich. Computations beyond exponentiation gates and applications. Electronic Colloquium on Computational Complexity (ECCC), 22:42, 2015."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/2512973"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90044-3"},{"key":"e_1_2_1_55_1","volume-title":"December","author":"Welch Lloyd R.","year":"1986","unstructured":"Lloyd R. Welch and Elwyn R. Berlekamp . Error correction for algebraic block codes , December 1986 . US Patent 4,633,470. Lloyd R. Welch and Elwyn R. Berlekamp. Error correction for algebraic block codes, December 1986. US Patent 4,633,470."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.95"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2852040.2852051","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2852040.2852051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:17Z","timestamp":1750222457000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2852040.2852051"}},"subtitle":["Challenges in Polynomial Factorization1"],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1145\/2852040.2852051"],"URL":"https:\/\/doi.org\/10.1145\/2852040.2852051","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2015,12]]},"assertion":[{"value":"2015-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}