Faster \(p\)-adic feasibility for certain multivariate sparse polynomials

DOI10.1016/j.jsc.2011.09.007zbMath1246.65078arXiv1010.5310MaRDI QIDQ412210

J. Herrera, H. S. Yoon

Publication date: 4 May 2012

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.5310

zbMATH Keywords

complexity; Newton polytope; Laurent polynomials; NP-completeness; feasibility; multivariate; sparse; fewnomial; trinomial; Hilbert's Tenth Problem; \(p\)-adic rational; \(p\)-adic rational root; Hensel's Lemma; short certificate; Wagstaff Conjecture

Mathematics Subject Classification ID

12D10: Polynomials in real and complex fields: location of zeros (algebraic theorems)

65Y20: Complexity and performance of numerical algorithms

65H04: Numerical computation of roots of polynomial equations

Related Items

Solvability of cubic equations in \(p\)-adic integers \((p>3)\)

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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting curves and their projections
• New NP-hard and NP-complete polynomial and integer divisibility problems
• Factoring polynomials with rational coefficients
• There are infinitely many Carmichael numbers
• Efficient \(p\)-adic cell decompositions for univariate polynomials
• Bounds for the roots of lacunary polynomials
• Straight-line programs and torsion points on elliptic curves
• Counting solutions to equations in many variables over finite fields
• PRIMES is in P
• An explicit algebraic family of genus-one curves violating the Hasse principle
• Implicit functions from topological vector spaces to Banach spaces
• Strictly local solutions of diophantine equations
• Cubic homogeneous polynomials over \(\mathfrak p\)-adic number fields
• Faster real feasibility via circuit discriminants
• Multivariate ultrametric root counting
• Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond
• Complexity estimates depending on condition and round-off error
• Computing zeta functions of nondegenerate curves
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Characterization of entire functions via quadrature
• Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus
• Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry
• Zeros of p -adic forms
• Heuristics for the Brauer–Manin Obstruction for Curves
• Diophantine Problems Over Local Fields I
• Decision procedures for real and p‐adic fields
• A CRITERION FOR THE p-ADIC SOLUBILITY OF DIOPHANTINE EQUATIONS
• Numbers of solutions of equations in finite fields
• Algorithms in real algebraic geometry