2026-07-22T06:32:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17402 2024-03-06T10:59:39Z ddc:004 open_access

On Solving Sparse Polynomial Factorization Related Problems Bisht, Pranav Volkovich, Ilya Sparse Polynomials Identity Testing Derandomization Factor-Sparsity Multivariate Polynomial Factorization In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first factor sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most s terms and individual degree bounded by d can itself have at most s^O(d²log n) terms. It is conjectured, though, that the "true" sparsity bound should be polynomial (i.e. s^poly(d)). In this paper we provide supporting evidence for this conjecture by presenting polynomial-time algorithms for several problems that would be implied by a polynomial-size sparsity bound. In particular, we give efficient (deterministic) algorithms for identity testing of Σ^[2]ΠΣΠ^[ind-deg d] circuits and testing if a sparse polynomial is an exact power. Hence, our algorithms rely on different techniques. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pranav Bisht and Ilya Volkovich 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.10 urn:nbn:de:0030-drops-174023 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.10 eng https://creativecommons.org/licenses/by/4.0/legalcode