  A sparse polynomial (also called a lacunary polynomial) is a polynomial that
has relatively few terms compared to its degree. The sparse-representation of a
polynomial represents the polynomial as a list of its non-zero terms
(coefficient-degree pairs). In particular, the degree of a sparse polynomial
can be exponential in the sparse-representation size.
  We prove that for monic polynomials $f, g \in \mathbb{C}[x]$ such that $g$
divides $f$, the $\ell_2$-norm of the quotient polynomial $f/g$ is bounded by
$\lVert f \rVert_1 \cdot \tilde{O}(\lVert{g}\rVert_0^3\text{deg}^2{
f})^{\lVert{g}\rVert_0 - 1}$. This improves upon the exponential (in
$\text{deg}{ f}$) bounds for general polynomials and implies that the trivial
long division algorithm runs in time quasi-linear in the input size and number
of terms of the quotient polynomial $f/g$, thus solving a long-standing problem
on exact divisibility of sparse polynomials.
  We also study the problem of bounding the number of terms of $f/g$ in some
special cases. When $f, g \in \mathbb{Z}[x]$ and $g$ is a cyclotomic-free
(i.e., it has no cyclotomic factors) trinomial, we prove that
$\lVert{f/g}\rVert_0 \leq O(\lVert{f}\rVert_0 \text{size}({f})^2 \cdot
\log^6{\text{deg}{ g}})$. When $g$ is a binomial with $g(\pm 1) \neq 0$, we
prove that the sparsity is at most $O(\lVert{f}\rVert_0 (
\log{\lVert{f}\rVert_0} + \log{\lVert{f}\rVert_{\infty}}))$. Both upper bounds
are polynomial in the input-size. We leverage these results and give a
polynomial time algorithm for deciding whether a cyclotomic-free trinomial
divides a sparse polynomial over the integers.
  As our last result, we present a polynomial time algorithm for testing
divisibility by pentanomials over small finite fields when $\text{deg}{ f} =
\tilde{O}(\text{deg}{ g})$.
