Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.9
URN: urn:nbn:de:0030-drops-174012
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17401/
Bisht, Pranav ; Saxena, Nitin
Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2022.9,
author = {Bisht, Pranav and Saxena, Nitin},
title = {{Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {9:1--9:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-261-7},
ISSN = {1868-8969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17401},
URN = {urn:nbn:de:0030-drops-174012},
doi = {10.4230/LIPIcs.FSTTCS.2022.9},
annote = {Keywords: Multivariate polynomial factorization, derandomization, sparse polynomials, symmetric polynomials, factor-sparsity, convex polytopes}
}
| Keywords: | Multivariate polynomial factorization, derandomization, sparse polynomials, symmetric polynomials, factor-sparsity, convex polytopes | |
| Seminar: | 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
