2026-07-23T21:24:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5346 2024-03-06T10:36:22Z ddc:004 open_access

Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials Volkovich, Ilya Derandomization Multivariate Polynomial Factorization Sparse polynomials We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors and sums of univariate polynomials. Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in [von zur Gathen/Kaltofen, J. Comp. Sys. Sci., 1985] to devise an efficient deterministic algorithm for factoring (general) sparse polynomials. We achieve our goal by introducing essential factorization schemes which can be thought of as a relaxation of the regular factorization notion. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilya Volkovich 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.943 urn:nbn:de:0030-drops-53469 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.943 eng https://creativecommons.org/licenses/by/3.0/legalcode