Yuyu Zhu

A complexity chasm for solving univariate sparse polynomial equations over $p$-adic fields

2020 · arXiv (Cornell University)

We reveal a complexity chasm, separating the trinomial and tetranomial cases, for solving univariate sparse polynomial equations over certain local fields. First, for any fixed field $K\in\{\mathbb{Q}_2,\mathbb{Q}_3,\mathbb{Q}_5,\ldots\}$, we prove that any polynomial $f\in\mathbb{Z}[x]$ with exactly …