Polynomial-time root-counting conjecture for fixed-arity sparse polynomials over $p$-adic fields

Let $p$ and $t$ be fixed, and let $f\in\mathbb{Z}[x_1]$ be an input $t$-nomial, meaning a univariate integer polynomial with at most $t$ monomial terms. Root-counting conjecture. There is a polynomial-time algorithm that counts the roots of $f$ in $\mathbb{Q}_p$. This conjecture proposes a tractable algorithm for root counting over $p$-adic fields when both the prime and the number of monomial terms are fixed. The paper establishes polynomial-time algorithms for related problems for trinomials and shows a complexity barrier for tetranomials with fixed $p$; counting points on trinomial curves over $\mathbb{F}_p$ in time $\log^{O(1)}(pd)$ is noted as a challenging open question.