This is the paper version of Roche’s ISSAC 2018 tutorial, which serves as an update to my work [1]. It is an excellent tutorial, written in a clear and accessible style. ISSAC is to be commended for these tutorials, and I wish more were published.

Sparse and dense polynomials are very different. Problems that are trivial for dense polynomials may be difficult for sparse polynomials. (This is similar to SAT, which is trivial for some dense representations and NP-complete for some sparse representations.) For sparse polynomials, greatest common divisor or even deciding relative primality [2] are NP-hard problems. The complexity of exact division is unsolved (open problem 3). Other problems take on a different shape, for example, factorization, where gap theorems mean that finding low-degree factors of sparse polynomials is a very different problem from finding high-degree factors.

There is an excellent bibliography of 87 items, well over half of which postdate my earlier work [1], so an update was clearly necessary.