Factors of low individual degree polynomials
From MaRDI portal
Publication:301529
DOI10.1007/s00037-016-0130-2zbMath1345.68292OpenAlexW2341723576MaRDI QIDQ301529
F. Blanchet-Sadri, M. Dambrine
Publication date: 30 June 2016
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5059/
Symbolic computation and algebraic computation (68W30) Polynomials in general fields (irreducibility, etc.) (12E05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, New Sparse Multivariate Polynomial Factorization Algorithms over Integers, Unnamed Item, On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree, Factorization of polynomials given by arithmetic branching programs, Unnamed Item, Factorization of polynomials given by arithmetic branching programs
Cites Work
- Unnamed Item
- Unnamed Item
- Factoring sparse multivariate polynomials
- Factoring polynomials with rational coefficients
- Decoding of Reed Solomon codes beyond the error-correction bound
- Equivalence of polynomial identity testing and polynomial factorization
- Arithmetic Circuits: A survey of recent results and open questions
- Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
- On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- A knapsack-type public key cryptosystem based on arithmetic in finite fields
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- Derandomizing polynomial identity tests means proving circuit lower bounds
