{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T17:26:41Z","timestamp":1673458001885},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"Simons Collaboration on Algorithms and Geometry"},{"name":"Sloan research fellowship"},{"name":"NSF","award":["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":"\n In this article, we study the problem of deterministic factorization of sparse polynomials. We show that if\n f<\/jats:italic>\n \u2208 F[\n x<\/jats:italic>\n 1<\/jats:sub>\n ,\n x<\/jats:italic>\n 2<\/jats:sub>\n ,\u2026 ,\n x<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n ] is a polynomial with s monomials, with individual degrees of its variables bounded by\n d<\/jats:italic>\n , then\n f<\/jats:italic>\n can be deterministically factored in time\n s<\/jats:italic>\n \n poly(\n d<\/jats:italic>\n )log\n 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 d<\/jats:italic>\n =1 and\n d<\/jats:italic>\n =2, only exponential time-deterministic factoring algorithms were known.\n <\/jats:p>\n \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 f<\/jats:italic>\n is an\n s<\/jats:italic>\n -sparse polynomial in\n n<\/jats:italic>\n variables, with individual degrees of its variables bounded by\n d<\/jats:italic>\n , then the sparsity of each factor of\n f<\/jats:italic>\n is bounded by\n s<\/jats:italic>\n \n (9\n d<\/jats:italic>\n 2<\/jats:sup>\n log\n n<\/jats:italic>\n )\n <\/jats:sup>\n . This is the first non-trivial bound on factor sparsity for\n d<\/jats:italic>\n > 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 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":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"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"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, New Jersey, USA"}]},{"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, Michigan, USA"}]}],"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\/pdf\/10.1145\/3365667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T07:06:24Z","timestamp":1672556784000},"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":"http:\/\/dx.doi.org\/10.1145\/3365667","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"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"}}]}}