Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields
From MaRDI portal
Publication:2816831
DOI10.1137/140990401zbMath1345.68281OpenAlexW2511762567MaRDI QIDQ2816831
Jingguo Bi, J. Maurice Rojas, Qi Cheng
Publication date: 26 August 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.298.3034
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Sparse univariate polynomials with many roots over finite fields ⋮ Computing zeta functions of large polynomial systems over finite fields ⋮ Value Sets of Sparse Polynomials
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Faster \(p\)-adic feasibility for certain multivariate sparse polynomials
- Counting curves and their projections
- Factoring bivariate sparse (lacunary) polynomials
- An explicit separation of relativised random polynomial time and relativised deterministic polynomial time
- New NP-hard and NP-complete polynomial and integer divisibility problems
- Factoring polynomials with rational coefficients
- A polynomial time algorithm for diophantine equations in one variable
- On finding primitive roots in finite fields
- Improved algorithms for computing determinants and resultants
- On solving univariate sparse polynomials in logarithmic time
- An uncertainty principle for cyclic groups of prime order
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Computing Frobenius maps and factoring polynomials
- An introduction to the geometry of numbers.
- An uncertainty inequality for finite Abelian groups.
- Improving exhaustive search implies superpolynomial lower bounds
- Faster real feasibility via circuit discriminants
- Counting Value Sets: Algorithm and Complexity
- Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
- Roots of sparse polynomials over a finite field
- Lattice Reduction Algorithms: Theory and Practice
- Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond
- Fast Polynomial Factorization and Modular Composition
- The Asymptotic Density of Some k-Dimensional Sets
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- A New Algorithm for Factoring Polynomials Over Finite Fields
- Subquadratic-time factoring of polynomials over finite fields
- On the complexity of factoring bivariate supersparse (Lacunary) polynomials
- Computational Complexity
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Factoring Polynomials Over Large Finite Fields
- Algorithms in real algebraic geometry
- Factoring polynomials over finite fields: A survey
- On the statistical properties of Diffie-Hellman distributions
- On the complexity of \(k\)-SAT