2024/10/26 by Holger Dell, Dell, Holger, Anselm Haak +5 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2410.20162
openalex publication_date 2024/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a randomized algorithm for solving low-degree polynomial equation systems over finite fields faster than exhaustive search. In order to do so, we follow a line of work by Lokshtanov, Paturi, Tamaki, Williams, and Yu (SODA 2017), Björklund, Kaski, and Williams (ICALP 2019), and Dinur (SODA 2021). In particular, we generalize Dinur's algorithm for \mathbbF2 to all finite fields, in particular the "symbolic interpolation" of Björklund, Kaski, and Williams, and we use an efficient trimmed multipoint evaluation and interpolation procedure for multivariate polynomials over finite fields by Van der Hoeven and Schost (AAECC 2013). The running time of our algorithm matches that of Dinur's algorithm for \mathbbF2 and is significantly faster than the one of Lokshtanov et al. for q>2. We complement our results with tight conditional lower bounds that, surprisingly, we were not able to find in the literature. In particular, under the strong exponential time hypothesis, we prove that it is impossible to solve n-variate low-degree polynomial equation systems over \mathbbFq in time O((q-ε)n). As a bonus, we show that under the counting version of the strong exponential time hypothesis, it is impossible to compute the number of roots of a single n-variate low-degree polynomial over \mathbbFq in time O((q-ε)n); this generalizes a result of Williams (SOSA 2018) from \mathbbF2 to all finite fields.