2026-07-27T16:24:38Z https://drops.dagstuhl.de/oai

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

Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials Bisht, Pranav Saxena, Nitin Multivariate polynomial factorization derandomization sparse polynomials symmetric polynomials factor-sparsity convex polytopes More than three decades ago, after a series of results, Kaltofen and Trager (J. Symb. Comput. 1990) designed a randomized polynomial time algorithm for factorization of multivariate circuits. Derandomizing this algorithm, even for restricted circuit classes, is an important open problem. In particular, the case of s-sparse polynomials, having individual degree d = O(1), is very well-studied (Shpilka, Volkovich ICALP'10; Volkovich RANDOM'17; Bhargava, Saraf and Volkovich FOCS'18, JACM'20). We give a complete derandomization for this class assuming that the input is a symmetric polynomial over rationals. Generally, we prove an s^poly(d)-sparsity bound for the factors of symmetric polynomials over any field. This characterizes the known worst-case examples of sparsity blow-up for sparse polynomial factoring. To factor f, we use techniques from convex geometry and exploit symmetry (only) in the Newton polytope of f. We prove a crucial result about convex polytopes, by introducing the concept of "low min-entropy", which might also be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pranav Bisht and Nitin Saxena 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.9 urn:nbn:de:0030-drops-174012 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.9 eng https://creativecommons.org/licenses/by/4.0/legalcode