11 citations · 38 across the 15 of their papers we have counts for
3 papers · 2 filters
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…
Sharp bounds for the number of roots of univariate fewnomials
Martin Avendano, Teresa Krick
Let K be a field and t>=0. Denote by Bm(t,K) the maximum number of non-zero roots in K, counted with multiplicities, of a non-zero polynomial in K[x] with at most t+1 monomial term…
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…