On solving sparse polynomial factorization related problems

DOI10.1007/S00037-025-00268-5MaRDI QIDQ6938574zbMATH OpenFDO

Authors Pranav Bisht, Ilya Volkovich

Publication date 25 August 2025

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00037-025-00268-5

zbMATH Keywords

derandomizationidentity testingsparse polynomialsfactor sparsitymultivariate polynomial factorization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites work

• scientific article; zbMATH DE number 6530429 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 108109 (Why is no real title available?)
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 7711593 (Why is no real title available?)
• A case of depth-3 identity testing, sparse factorization and duality
• A knapsack-type public key cryptosystem based on arithmetic in finite fields
• A local decision test for sparse polynomials
• A probabilistic remark on algebraic program testing
• An elementary approach to subresultants theory.
• Arithmetic circuits: a survey of recent results and open questions
• Black-box identity testing of depth-4 multilinear circuits
• Bootstrapping variables in algebraic circuits
• Combinatorial Nullstellensatz
• 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
• Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials
• Derandomizing multivariate polynomial factoring for low degree factors
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic algorithms for low degree factors of constant depth circuits
• Deterministic divisibility testing via shifted partial derivatives
• Deterministic factorization of sparse polynomials with bounded individual degree
• Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials
• Factoring polynomials with rational coefficients
• Factoring sparse multivariate polynomials
• Factorization of polynomials given by arithmetic branching programs
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Ideals, Varieties, and Algorithms
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Modern computer algebra
• On solving sparse polynomial factorization related problems
• On some computations on sparse polynomials
• On the relation between polynomial identity testing and finding variable disjoint factors
• Polynomial time deterministic identity testing algorithm for Σ ^[3] ΠΣΠ ^[2] circuits via Edelstein–Kelly type theorem for quadratic polynomials
• Pseudorandom generators without the XOR lemma
• Randomness efficient identity testing of multivariate polynomials
• Read-once polynomial identity testing
• Towards identity testing for sums of products of Read-once and multilinear bounded-Read formulae

This page was built for publication: On solving sparse polynomial factorization related problems

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