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

DOI10.1016/j.jsc.2011.09.007zbMath1246.65078arXiv1010.5310OpenAlexW2963445336MaRDI 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

complexityNewton polytopeLaurent polynomialsNP-completenessfeasibilitymultivariatesparsefewnomialtrinomialHilbert's Tenth Problem\(p\)-adic rational\(p\)-adic rational rootHensel's Lemmashort certificateWagstaff Conjecture

Mathematics Subject Classification ID

Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04)

Related Items

Solvability of cubic equations in \(p\)-adic integers \((p>3)\), Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields, Computing zeta functions of large polynomial systems over finite fields, Counting roots for polynomials modulo prime powers, Recurrent properties of quasi-periodic dynamical systems with multiple frequencies of \(p\)-adic Liouville numbers, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Randomized polynomial-time root counting in prime power rings, On cubic equations over p-adic fields

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