What is it about?
Polynomial Factorization is a classical algebraic problem with a computational flavour. Finding efficient deterministic factorization algorithms even for sparse polynomials is a challenging open problem. We show how to solve it for the case of sparse polynomials which are symmetric. We use an interesting geometric connection to achieve our results.
Featured Image
Photo by D koi on Unsplash
Why is it important?
It is the first deterministic polynomial-time factorization algorithms for sparse polynomials that are symmetric and have constant individual degree. Our work use ideas from convex geometry, in particular, we show that a symmetric polytope has very few corner points (vertices).
Perspectives
We use an elegant, clever argument to show that a symmetric convex polytope has significantly less vertices (corner points). We prove this by switching to the hyperplane representation of polytopes, instead of the previously used vertex reporesentation in earlier works. Using the Newton polytopes, we then argue that if a sparse symmetric polynomial is multiplied by any other non-zero polynomial, not there cannot be too many cancellation of terms. In other words, a symmetric sparse polynomial cannot have dense factors. This structural resut is then used to derive efficient factorization algorithms.
Pranav Bisht
Indian School of Mines
Read the Original
This page is a summary of: Derandomization via Symmetric Polytopes: Poly-time Factorization of Certain Sparse Polynomials, ACM Transactions on Computation Theory, April 2025, ACM (Association for Computing Machinery),
DOI: 10.1145/3719022.
You can read the full text:
Contributors
The following have contributed to this page
