Derandomization via Symmetric Polytopes: Poly-time Factorization of Certain Sparse Polynomials

More than three decades ago, after a series of results, Kaltofen and Trager in 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), has been very well studied (e.g., by Shpilka and Volkovich in 2010, Vokovich in 2017, and Bhargava et al. in 2018). 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. 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.