3 citations · 6 across the 5 of their papers we have counts for
3 papers · 1 filter
Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials
Martín Avendaño, Ashraf Ibrahim, J. Maurice Rojas +1
We present algorithms revealing new families of polynomials allowing sub-exponential detection of p-adic rational roots, relative to the sparse encoding. For instance, we show that…
Near NP-Completeness for Detecting p-adic Rational Roots in One Variable
Martin Avendano, Ashraf Ibrahim, J. Maurice Rojas +1
We show that deciding whether a sparse univariate polynomial has a p-adic rational root can be done in NP for most inputs. We also prove a polynomial-time upper bound for trinomial…
Algorithmic Arithmetic Fewnomial Theory I: One Variable
Ashraf Ibrahim, J. Maurice Rojas, Korben Rusek
Withdrawn by the authors due to an error in the proof of the finite field result (Thm. 1.5): The random primes used in the proof need NOT avoid the exceptional primes from Lemma 2.…