{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T19:50:04Z","timestamp":1773085804651,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T00:00:00Z","timestamp":1588204800000},"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":"Sloan research fellowship"},{"name":"NSF","award":["CCF-1350572 and CCF-1540634"],"award-info":[{"award-number":["CCF-1350572 and CCF-1540634"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            In this article, we study the problem of deterministic factorization of sparse polynomials. We show that if\n            <jats:italic>f<\/jats:italic>\n            \u2208 F[\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            ,\u2026 ,\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            ] is a polynomial with s monomials, with individual degrees of its variables bounded by\n            <jats:italic>d<\/jats:italic>\n            , then\n            <jats:italic>f<\/jats:italic>\n            can be deterministically factored in time\n            <jats:italic>s<\/jats:italic>\n            <jats:sup>\n              poly(\n              <jats:italic>d<\/jats:italic>\n              )log\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            . Prior to our work, the only efficient factoring algorithms known for this class of polynomials were randomized, and other than for the cases of\n            <jats:italic>d<\/jats:italic>\n            =1 and\n            <jats:italic>d<\/jats:italic>\n            =2, only exponential time-deterministic factoring algorithms were known.\n          <\/jats:p>\n          <jats:p>\n            A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular, we show that if\n            <jats:italic>f<\/jats:italic>\n            is an\n            <jats:italic>s<\/jats:italic>\n            -sparse polynomial in\n            <jats:italic>n<\/jats:italic>\n            variables, with individual degrees of its variables bounded by\n            <jats:italic>d<\/jats:italic>\n            , then the sparsity of each factor of\n            <jats:italic>f<\/jats:italic>\n            is bounded by\n            <jats:italic>s<\/jats:italic>\n            <jats:sup>\n              (9\n              <jats:italic>d<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            . This is the first non-trivial bound on factor sparsity for\n            <jats:italic>d<\/jats:italic>\n            &gt; 2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Carath\u00e9odory\u2019s Theorem.\n          <\/jats:p>\n          <jats:p>Our work addresses and partially answers a question of von zur Gathen and Kaltofen [1985] who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials.<\/jats:p>","DOI":"10.1145\/3365667","type":"journal-article","created":{"date-parts":[[2020,5,5]],"date-time":"2020-05-05T04:22:53Z","timestamp":1588652573000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree"],"prefix":"10.1145","volume":"67","author":[{"given":"Vishwas","family":"Bhargava","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, New Jersey, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, New Jersey, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746566"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.21214"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 30th Conference on Computational Complexity (CCC). 198--216","author":"Mendes de Oliveira R.","year":"2015"},{"key":"e_1_2_1_5_1","volume-title":"Factors of sparse polynomials are sparse. CoRR abs\/1404.4834","author":"Dvir Z.","year":"2014"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2852040.2852051"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2004.05.004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen. 2006. Who was who in polynomial factorization. In ISSAC. 2.  J. von zur Gathen. 2006. Who was who in polynomial factorization. In ISSAC. 2.","DOI":"10.1145\/1145768.1145770"},{"key":"e_1_2_1_9_1","unstructured":"J. von zur Gathen and J. Gerhard. 1999. Modern Computer Algebra. Cambridge University Press.  J. von zur Gathen and J. Gerhard. 1999. Modern Computer Algebra. Cambridge University Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90044-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"K. O. Geddes S. R. Czapor and G. Labahn. 1992. Algorithms for Computer Algebra. Kluwer.  K. O. Geddes S. R. Czapor and G. Labahn. 1992. Algorithms for Computer Algebra. Kluwer.","DOI":"10.1007\/b102438"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"V. Guruswami and M. Sudan. 1999. Improved decoding of Reed-Solomon codes and algebraic-geometry codes. IEEE Transactions on Information Theory 45(6) (1999) 1757--1767.  V. Guruswami and M. Sudan. 1999. Improved decoding of Reed-Solomon codes and algebraic-geometry codes. IEEE Transactions on Information Theory 45(6) (1999) 1757--1767.","DOI":"10.1109\/18.782097"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28443"},{"key":"e_1_2_1_15_1","volume-title":"Randomness in Computation","author":"Kaltofen E."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"E. Kaltofen. 2003. Polynomial factorization: A success story. In ISSAC. 3--4.  E. Kaltofen. 2003. Polynomial factorization: A success story. In ISSAC. 3--4.","DOI":"10.1145\/860854.860857"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). 216--223","author":"Klivans A."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC). 169--180","author":"Kopparty S.","year":"2014"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_2_1_22_1","first-page":"98","article-title":"On the significance of the theory of convex polyhedra for formal algebra","volume":"30","author":"Ostrowski A. M.","year":"1922","journal-title":"Annual Reports German Math. Association"},{"key":"e_1_2_1_23_1","unstructured":"R. Saptharishi. 2018. Private communication.  R. Saptharishi. 2018. Private communication."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC). 421--430","author":"Saraf S.","year":"2011"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","volume-title":"Polynomials with Special Regard to Reducibility","author":"Schinzel A.","DOI":"10.1017\/CBO9780511542916"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"V. Shoup. 1991. A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In ISSAC. 14--21.  V. Shoup. 1991. A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In ISSAC. 14--21.","DOI":"10.1145\/120694.120697"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"A. Shpilka and I. Volkovich. 2009. Improved polynomial identity testing for read-once formulas. In APPROX-RANDOM. 700--713. Full version at https:\/\/eccc.weizmann.ac.il\/report\/2010\/011.  A. Shpilka and I. Volkovich. 2009. Improved polynomial identity testing for read-once formulas. In APPROX-RANDOM. 700--713. Full version at https:\/\/eccc.weizmann.ac.il\/report\/2010\/011.","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP). 408--419","author":"Shpilka A.","year":"2010"},{"key":"e_1_2_1_29_1","volume-title":"Decoding of Reed-Solomon codes beyond the error-correction bound. Journal of Complexity 13(1)","author":"Sudan M.","year":"1997"},{"key":"e_1_2_1_30_1","unstructured":"M. Sudan. 1998. Algebra and Computation. http:\/\/people.csail.mit.edu\/madhu\/FT98\/course.html Lecture notes.  M. Sudan. 1998. Algebra and Computation. http:\/\/people.csail.mit.edu\/madhu\/FT98\/course.html Lecture notes."},{"key":"e_1_2_1_31_1","unstructured":"I. Volkovich. 2015. Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials. In APPROX-RANDOM. 943--958.  I. Volkovich. 2015. Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials. In APPROX-RANDOM. 943--958."},{"key":"e_1_2_1_32_1","first-page":"1","article-title":"On some computations on sparse polynomials","volume":"48","author":"Volkovich I.","year":"2017","journal-title":"APPROX-RANDOM."},{"key":"e_1_2_1_33_1","volume-title":"Lectures on Polytopes","author":"Ziegler G. M."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365667","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:21Z","timestamp":1750203861000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,30]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3365667"],"URL":"https:\/\/doi.org\/10.1145\/3365667","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,30]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}