{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:32Z","timestamp":1754152292733,"version":"3.41.2"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s00037-025-00268-5","type":"journal-article","created":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T09:27:44Z","timestamp":1752139664000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Solving Sparse Polynomial Factorization Related Problems"],"prefix":"10.1007","volume":"34","author":[{"given":"Pranav","family":"Bisht","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,9]]},"reference":[{"key":"268_CR1","doi-asserted-by":"crossref","unstructured":"M. Agrawal, S. Ghosh & N. Saxena (2019). Bootstrapping variables\nin algebraic circuits. Proceedings of the National Academy of Sciences\n116(17), 8107\u20138118.","DOI":"10.1073\/pnas.1901272116"},{"key":"268_CR2","doi-asserted-by":"crossref","unstructured":"M. Agrawal & V. Vinay (2008). Arithmetic circuits: A chasm at\ndepth four. In Proceedings of the 49th Annual IEEE Symposium on\nFoundations of Computer Science (FOCS), 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"key":"268_CR3","doi-asserted-by":"crossref","unstructured":"N. Alon (1999). Combinatorial Nullstellensatz. Combinatorics, Probability\nand Computing 8, 7\u201329.","DOI":"10.1017\/S0963548398003411"},{"key":"268_CR4","unstructured":"F. Ap\u00e9ry & J.P. Jouanolou (2006). R\u00e9sultant et sous-r\u00e9sultants: le\ncas d\u2019une variable: avec exercices corrig\u00e9s. Hermann."},{"key":"268_CR5","doi-asserted-by":"crossref","unstructured":"M. Ben-Or & P. Tiwari (1988). A Deterministic Algorithm for Sparse\nMultivariate Polynominal Interpolation. In Proceedings of the 20th Annual\nACM Symposium on Theory of Computing (STOC), 301\u2013309.","DOI":"10.1145\/62212.62241"},{"key":"268_CR6","doi-asserted-by":"crossref","unstructured":"C. S. Bhargav, P. Dwivedi & N. Saxena (2024). Learning the Coefficients:\nA Presentable Version of Border Complexity and Applications\nto Circuit Factoring. In Proceedings of the 56th Annual ACM Symposium\non Theory of Computing, STOC 2024, Vancouver, BC, Canada,\nJune 24-28, 2024, 130\u2013140. ACM. URL https:\/\/doi.org\/10.1145\/3618260.3649743.","DOI":"10.1145\/3618260.3649743"},{"key":"268_CR7","doi-asserted-by":"crossref","unstructured":"V. Bhargava, S. Saraf & I. Volkovich (2020). Deterministic Factorization\nof Sparse Polynomials with Bounded Individual Degree. J.\nACM 67(2), 8:1\u20138:28.","DOI":"10.1145\/3365667"},{"key":"268_CR8","unstructured":"P. Bisht, N. Gupta & I. Volkovich (2023). Towards Identity Testing\nfor Sums of Products of Read-Once and Multilinear Bounded-Read\nFormulae. In 43rd IARCS Annual Conference on Foundations of Software\nTechnology and Theoretical Computer Science, FSTTCS 2023, December\n18-20, 2023, IIIT Hyderabad, Telangana, India, volume 284 of\nLIPIcs, 9:1\u20139:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik.\nURL https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2023.9. Full version\navailable at https:\/\/eccc.weizmann.ac.il\/report\/2023\/109\/."},{"key":"268_CR9","unstructured":"P. Bisht & N. Saxena (2022). Derandomization via symmetric\npolytopes: Poly-timefactorization of certain sparse polynomials.\nIn Proceedings of the 42nd IARCS Annual Conference on\nFoundations of Software Technology and Theoretical Computer Science\n(FSTTCS). URL https:\/\/www.cse.iitk.ac.in\/users\/nitin\/papers\/symmetricSparse.pdf."},{"key":"268_CR10","unstructured":"P. Bisht & I. Volkovich (2022). On Solving Sparse Polynomial\nFactorization Related Problems. In 42nd IARCS Annual Conference\non Foundations of Software Technology and Theoretical Computer Science,\nFSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai,\nIndia, volume 250 of LIPIcs, 10:1\u201310:22. Schloss Dagstuhl - Leibniz-\nZentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2022.10."},{"key":"268_CR11","doi-asserted-by":"crossref","unstructured":"B. Chor & R. L. Rivest (1988). A knapsack-type public key cryptosystem\nbased on arithmetic in finite fields. IEEE Transactions on\nInformation Theory 34(5), 901\u2013909.","DOI":"10.1109\/18.21214"},{"key":"268_CR12","doi-asserted-by":"crossref","unstructured":"D. A. Cox, J. Little & D. O\u2019Shea (2015). Ideals, varieties, and\nalgorithms - an introduction to computational algebraic geometry and\ncommutative algebra (4. ed.). Undergraduate texts in mathematics.\nSpringer.","DOI":"10.1007\/978-3-319-16721-3"},{"key":"268_CR13","doi-asserted-by":"crossref","unstructured":"R. A. DeMillo & R. J. Lipton (1978). A Probabilistic Remark on\nAlgebraic Program Testing. Inf. Process. Lett. 7(4), 193\u2013195.","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"268_CR14","unstructured":"P. Dutta (2018). Discovering the roots: Unifying and extending results\non multivariate polynomial factoring in algebraic complexity. Master\u2019s\nthesis, Chennai Mathematical Institute ."},{"key":"268_CR15","unstructured":"P. Dutta, P. Dwivedi & N. Saxena (2021). Deterministic identity\ntesting paradigms for bounded top-fanin depth-4 circuits. In 36th\nConference on Computational Complexity (CCC 2021), volume 5, 9."},{"key":"268_CR16","unstructured":"P. Dutta, A. Sinhababu & T. Thierauf (2024). Derandomizing\nMultivariate Polynomial Factoring for Low Degree Factors. In Approximation,\nRandomization, and Combinatorial Optimization. Algorithms\nand Techniques, APPROX\/RANDOM 2024, August 28-30, 2024, London\nSchool of Economics, London, UK, A. Kumar & N. Ron-Zewi,\neditors, volume 317 of LIPIcs, 75:1\u201375:20. Schloss Dagstuhl - Leibniz-\nZentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2024.75."},{"key":"268_CR17","doi-asserted-by":"crossref","unstructured":"M. A. Forbes (2015). Deterministic divisibility testing via shifted partial\nderivatives. In 2015 IEEE 56th Annual Symposium on Foundations\nof Computer Science. 451\u2013465. IEEE.","DOI":"10.1109\/FOCS.2015.35"},{"key":"268_CR18","unstructured":"J. von zur Gathen & J. Gerhard (1999). Modern computer algebra.\nCambridge University Press."},{"key":"268_CR19","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen & E. Kaltofen (1985). Factoring Sparse Multivariate\nPolynomials. Journal of Computer and System Sciences 31(2),\n265\u2013287. URL http:\/\/dx.doi.org\/10.1016\/0022-0000(85)90044-3.","DOI":"10.1016\/0022-0000(85)90044-3"},{"key":"268_CR20","doi-asserted-by":"crossref","unstructured":"K. O. Geddes, S. R. Czapor & G. Labahn (1992). Algorithms for\ncomputer algebra. Kluwer. ISBN 978-0-7923-9259-0.","DOI":"10.1007\/b102438"},{"key":"268_CR21","doi-asserted-by":"crossref","unstructured":"E. Grigorescu, K. Jung & R. Rubinfeld (2010). A local decision\ntest for sparse polynomials. Inf. Process. Lett. 110(20), 898\u2013901. URL\nhttp:\/\/dx.doi.org\/10.1016\/j.ipl.2010.07.012.","DOI":"10.1016\/j.ipl.2010.07.012"},{"key":"268_CR22","doi-asserted-by":"crossref","unstructured":"V. Guruswami & M. Sudan (1999). Improved decoding of Reed-\nSolomon codes and algebraic-geometry codes. IEEE Transactions on\nInformation Theory 45(6), 1757\u20131767.","DOI":"10.1109\/18.782097"},{"key":"268_CR23","doi-asserted-by":"crossref","unstructured":"V. Kabanets & R. Impagliazzo (2004). Derandomizing Polynomial\nIdentity Tests Means Proving Circuit Lower Bounds. Computational\nComplexity 13(1-2), 1\u201346.","DOI":"10.1007\/s00037-004-0182-6"},{"key":"268_CR24","doi-asserted-by":"crossref","unstructured":"M. El Kahoui (2003). An elementary approach to subresultants theory.\nJournal of Symbolic Computation 35(3), 281\u2013292.","DOI":"10.1016\/S0747-7171(02)00135-9"},{"key":"268_CR25","unstructured":"E. Kaltofen (1989). Factorization of polynomials given by straightline\nprograms. In Randomness in Computation, S. Micali, editor,\nvolume 5 of Advances in Computing Research, 375\u2013412. JAI Press Inc.,\nGreenwhich, Connecticut."},{"key":"268_CR26","doi-asserted-by":"crossref","unstructured":"E. Kaltofen & B. M. Trager (1990). Computing with Polynomials\nGiven by Black Boxes for Their Evaluations: Greatest Common Divisors,\nFactorization, Separation of Numerators and Denominators. J. of\nSymbolic Computation 9(3), 301\u2013320.","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"268_CR27","doi-asserted-by":"crossref","unstructured":"A. Klivans & D. Spielman (2001). Randomness efficient identity\ntesting of multivariate polynomials. In Proceedings of the 33rd Annual\nACM Symposium on Theory of Computing (STOC), 216\u2013223.","DOI":"10.1145\/380752.380801"},{"key":"268_CR28","doi-asserted-by":"crossref","unstructured":"M. Kumar, V. Ramanathan & R. Saptharishi (2024a). Deterministic\nAlgorithms for Low Degree Factors of Constant Depth Circuits.\nIn Proceedings of the 2024 ACM-SIAM Symposium on Discrete\nAlgorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024,\nDavid P. Woodruff, editor, 3901\u20133918. SIAM. URL https:\/\/doi.org\/10.1137\/1.9781611977912.137.","DOI":"10.1137\/1.9781611977912.137"},{"key":"268_CR29","doi-asserted-by":"crossref","unstructured":"M. Kumar, V. Ramanathan, R. Saptharishi & B. L. Volk\n(2024b). Towards Deterministic Algorithms for Constant-Depth Factors\nof Constant-Depth Circuits. CoRR abs\/2403.01965. URL https:\/\/doi.org\/10.48550\/arXiv.2403.01965.","DOI":"10.1137\/1.9781611977912.137"},{"key":"268_CR30","doi-asserted-by":"crossref","unstructured":"A.K. Lenstra, H.W. Lenstr & L. Lov\u00e1sz (1982). Factoring polynomials\nwith rational coefficients. Mathematische Annalen, 261(4), 515\u2013\n534.","DOI":"10.1007\/BF01457454"},{"key":"268_CR31","doi-asserted-by":"crossref","unstructured":"N. Limaye, S. Srinivasan & S. Tavenas (2022). Superpolynomial\nlower bounds against low-depth algebraic circuits. Communications of\nthe ACM, 67(2), 101\u2013108.","DOI":"10.1145\/3611094"},{"key":"268_CR32","doi-asserted-by":"crossref","unstructured":"S. Peleg & A. Shpilka (2021). Polynomial time deterministic identity\ntesting algorithm for $$\\Sigma^{[3]}\\Pi\\Sigma\\Pi^{[2]}$$ circuits via Edelstein\u2013Kelly type\ntheorem for quadratic polynomials. In Proceedings of the 53rd Annual\nACM SIGACT Symposium on Theory of Computing, 259\u2013271.","DOI":"10.1145\/3406325.3451013"},{"key":"268_CR33","doi-asserted-by":"crossref","unstructured":"C. Saha, R. Saptharishi & N. Saxena (2013). A Case of Depth-\n3 Identity Testing, Sparse Factorization and Duality. Computational\nComplexity 22(1), 39\u201369. URL http:\/\/dx.doi.org\/10.1007\/s00037-012-0054-4.","DOI":"10.1007\/s00037-012-0054-4"},{"key":"268_CR34","doi-asserted-by":"crossref","unstructured":"S. Saraf & I. Volkovich (2018). Blackbox Identity Testing for\nDepth-4 Multilinear Circuits. Combinatorica 38(5), 1205\u20131238.","DOI":"10.1007\/s00493-016-3460-4"},{"key":"268_CR35","doi-asserted-by":"crossref","unstructured":"J. T. Schwartz (1980). Fast probabilistic algorithms for verification\nof polynomial identities. J. ACM 27(4), 701\u2013717.","DOI":"10.1145\/322217.322225"},{"key":"268_CR36","doi-asserted-by":"crossref","unstructured":"A. Shpilka & I. Volkovich (2010). On the Relation between\nPolynomial Identity Testing and Finding Variable Disjoint\nFactors. In Automata, Languages and Programming, 37th\nInternational Colloquium (ICALP), 408\u2013419. Full version at\nhttps:\/\/eccc.weizmann.ac.il\/report\/2010\/036.","DOI":"10.1007\/978-3-642-14165-2_35"},{"key":"268_CR37","doi-asserted-by":"crossref","unstructured":"A. Shpilka & I. Volkovich (2015). Read-Once Polynomial Identity\nTesting. Computational Complexity 24(3), 477\u2013532.","DOI":"10.1007\/s00037-015-0105-8"},{"key":"268_CR38","doi-asserted-by":"crossref","unstructured":"A. Shpilka & A. Yehudayoff (2010). Arithmetic Circuits: A survey\nof recent results and open questions. Foundations and Trends in\nTheoretical Computer Science 5(3-4), 207\u2013388.","DOI":"10.1561\/0400000039"},{"key":"268_CR39","doi-asserted-by":"crossref","unstructured":"A. Sinhababu & T. Thierauf (2021). Factorization of polynomials\ngiven by arithmetic branching programs. computational complexity\n30(2), 1\u201347.","DOI":"10.1007\/s00037-021-00215-0"},{"key":"268_CR40","doi-asserted-by":"crossref","unstructured":"V. Strassen (1973). Vermeidung von Divisionen. J. of Reine Angew.\nMath. 264, 182\u2013202.","DOI":"10.1515\/crll.1973.264.184"},{"key":"268_CR41","doi-asserted-by":"crossref","unstructured":"M. Sudan (1997). Decoding of Reed Solomon codes beyond the errorcorrection\nbound. Journal of Complexity 13(1), 180\u2013193.","DOI":"10.1006\/jcom.1997.0439"},{"key":"268_CR42","doi-asserted-by":"crossref","unstructured":"M. Sudan, L. Trevisan & S. P. Vadhan (2001). Pseudorandom\nGenerators without the XOR Lemma. J. Comput. Syst. Sci. 62(2),\n236\u2013266. URL http:\/\/dx.doi.org\/10.1006\/jcss.2000.1730.","DOI":"10.1006\/jcss.2000.1730"},{"key":"268_CR43","unstructured":"I. Volkovich (2015). Deterministically Factoring Sparse Polynomials\ninto Multilinear Factors and Sums of Univariate Polynomials. In\nApproximation, Randomization, and Combinatorial Optimization. Algorithms\nand Techniques (APPROX\/RANDOM 2015), Leibniz International\nProceedings in Informatics (LIPIcs), Vol. 20, Schloss Dagstuhl,\nLeibniz-Zentrum f\u00fcr Informatik: Dagstuhl, Germany. URL https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.943"},{"key":"268_CR44","unstructured":"I. Volkovich (2017). On some Computations on Sparse Polynomials.\nIn On Some Computations on Sparse Polynomials. In Approximation,\nRandomization, and Combinatorial Optimization. Algorithms\nand Techniques (APPROX\/RANDOM 2017). Leibniz International\nProceedings in Informatics (LIPIcs), Vol 81, pp. 48:1\u201348:21,\nSchloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.48"},{"key":"268_CR45","doi-asserted-by":"crossref","unstructured":"R. Zippel (1979). Probabilistic algorithms for sparse polynomials. In\nProceedings of the International Symposium on Symbolic and Algebraic\nComputation, 216\u2013226.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00268-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00268-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00268-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T23:10:54Z","timestamp":1753139454000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00268-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["268"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00268-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"10 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}