Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications

• Published in: Journal of the ACM 2023-12, Vol.70 (6), p.1-46, Article 42
• Main Authors: Bhargava, Vishwas, Ghosh, Sumanta, Kumar, Mrinal, Mohapatra, Chandra Kanta
• Format: Article
• Language: English
• Subjects: Algebra; Algebraic complexity theory; Algorithms; Complexity; Computer algebra; Data structures; Fields (mathematics); Fourier transforms; Linear circuits; Matrices (mathematics); Matrix algebra; Multivariate analysis; Polynomials; Questions; Theory of computation; Upper bounds
• ISSN: 0004-5411; 1557-735X
• DOI: 10.1145/3625226

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions such as polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck [7], fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state-of-the-art for this problem, Umans [25] and Kedlaya & Umans [16] gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields, respectively, provided that the number of variables n is at most \(d^{o(1)}\) where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case (i.e., \(n \notin d^{o(1)}\) ) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field \(\mathbb {F}_{q}\) of characteristic p, which evaluates an n-variate polynomial of degree less than d in each variable on N inputs in time \(\begin{equation*} \left((N + d^n)^{1 + o(1)}\text{poly}(\log q, d, n, p)\right), \end{equation*}\) provided that p is at most do(1), and q is at most (exp (exp (exp (...(exp (d))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g., n ∉ do(1)), this is the first nearly linear time algorithm for this problem over any (large enough) field. Our algorithm is based on elementary algebraic ideas, and this algebraic structure naturally leads to the following two independently interesting applications: — We show that there is an algebraic data structure for univariate polynomial evaluation with nearly linear space complexity and sublinear time complexity over finite fields of small characteristic and quasipolynomially bounded size. This provides a counterexample to a conjecture of Miltersen [21] who conjectured that over small finite fields, any algebraic data structure for polynomial evaluation using polynomial space must have linear query complexity. — We also show that over finite fields of small characteristic and quasipolynomi