Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials

DOI10.1145/3719022MaRDI QIDQ6949656zbMATH OpenFDO

Authors Pranav Bisht, Nitin Saxena

Publication date 1 August 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

Full work available at URL https://doi.org/10.1145/3719022

zbMATH Keywords

convex polytopesderandomizationfactor-sparsitymultivariate polynomial factorizationsparse polynomialssymmetric polynomials

Mathematics Subject Classification ID

Computational methods for problems pertaining to field theory (12-08) Polynomials in general fields (irreducibility, etc.) (12E05) Computational aspects related to convexity (52B55) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Cites work

• A knapsack-type public key cryptosystem based on arithmetic in finite fields
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Affine projections of symmetric polynomials.
• Closure results for polynomial factorization
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Decoding of Reed Solomon codes beyond the error-correction bound
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic factorization of sparse polynomials with bounded individual degree
• Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials
• Discovering the roots: uniform closure results for algebraic classes under factoring
• Factoring polynomials with rational coefficients
• Factoring sparse multivariate polynomials
• Factorization of polynomials given by arithmetic branching programs
• Factors of low individual degree polynomials
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Homogeneous formulas and symmetric polynomials
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 1467743 (Why is no real title available?)
• scientific article; zbMATH DE number 2151173 (Why is no real title available?)
• scientific article; zbMATH DE number 7561742 (Why is no real title available?)
• scientific article; zbMATH DE number 3265895 (Why is no real title available?)
• scientific article; zbMATH DE number 7829284 (Why is no real title available?)
• Improved decoding of Reed-Solomon and algebraic-geometric codes
• Modern computer algebra
• On some computations on sparse polynomials
• On the relation between polynomial identity testing and finding variable disjoint factors
• Randomness efficient identity testing of multivariate polynomials
• Superpolynomial lower bounds against low-depth algebraic circuits
• The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
• Über die Bedeutung der konvexen Polyeder für die formale Algebra.
• Über höhere Kongruenzen.

This page was built for publication: Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6949656)