What Can (and Can't) we Do with Sparse Polynomials?

Abstract

Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have efficient algorithms to handle them. However, with this compact storage comes new algorithmic challenges, as fast algorithms for dense polynomials may no longer be efficient. In this tutorial we examine the state of the art for sparse polynomial algorithms in three areas: arithmetic, interpolation, and factorization. The aim is to highlight recent progress both in theory and in practice, as well as opportunities for future work.

Tutorial at ISSAC 2018, Pages 25-30 of proceedings, In Proc. 43rd International Symposium on Symbolic and Algebraic Computation, ISSAC '18. ACM, New York, NY, 2018

References in corpus (1)

• Bounded-degree factors of lacunary multivariate polynomials

Cited by in corpus (5)

• Sparse Polynomial Interpolation and Division in Soft-linear Time
• Essentially Optimal Sparse Polynomial Multiplication
• Secure Outsourced Decryption for FHE-based Privacy-preserving Cloud Computing
• On exact division and divisibility testing for sparse polynomials
• A New Bound on Cofactors of Sparse Polynomials