TL;DR
This paper introduces highly efficient algorithms for interpolating sparse black-box polynomials when their coefficients are known to belong to a finite set (such as bounded rational numbers). By leveraging a single evaluation at a massive value for univariate polynomials and a clever "modified Kronecker substitution" for multivariate ones, the authors achieve optimal polynomial bit-size complexity, dramatically improving upon the exponential blowup seen in classical methods.
What Problem Does This Paper Address?
Imagine you have a "black box" mathematical function. You can feed it inputs and observe the outputs, and you know the hidden function is a polynomial with relatively few terms (it is "sparse"). Your goal is to figure out the exact algebraic formula of this polynomial. This is the classic problem of sparse polynomial interpolation.
While algorithms exist to solve this, they often struggle with exponential blowups in the size of the numbers involved or the degrees of the polynomials, especially in multivariate cases. However, in many real-world applications (like interpolating rational functions), we have extra prior knowledge: we know the polynomial's coefficients come from a specific, finite set—for example, integers bounded by a certain size, or rational numbers with bounded denominators. The authors tackle the question: How can we exploit this prior knowledge to make sparse interpolation significantly faster and more memory-efficient?
Methods
The authors propose two main algorithmic breakthroughs, splitting the problem into univariate (one variable) and multivariate (many variables) cases:
-
The Univariate "Giant Step" Algorithm: If the coefficients are bounded, the authors prove you only need a single evaluation to recover the entire univariate polynomial. They evaluate the black box at a carefully chosen, sufficiently large number $\beta$. Because $\beta$ is so large, the value of the highest-degree term completely dominates the sum of all lower-degree terms. The algorithm calculates the highest degree, extracts its coefficient, subtracts that term's value from the total, and repeats the process until the polynomial is fully reconstructed.
-
Modified Kronecker Substitution for Multivariate Polynomials: To handle multiple variables, mathematicians typically use a "Kronecker substitution" (e.g., replacing $x_i$ with $x^{(D+1)^{i-1}}$) to flatten a multivariate polynomial into a univariate one. The problem? The degree of the resulting univariate polynomial grows exponentially with the number of variables. The authors fix this by introducing a modified Kronecker substitution: they take the exponent modulo a prime number $p$. This keeps the degree of the resulting univariate polynomial small. As long as they find a "good prime" $p$ that doesn't cause two different multivariate terms to collide into the same univariate term, the problem is cleanly reduced to the univariate algorithm. They provide both a deterministic method (testing a batch of primes) and a faster probabilistic method (picking a random prime) to find this good prime.
Datasets
Not discussed in the paper in the context of standard machine learning benchmarks. The authors evaluated their algorithms using randomly constructed polynomials in the Maple computer algebra system to measure average running times.
Key Insights and Ideas
- Polynomials as Base-$\beta$ Numbers: The univariate algorithm essentially treats the polynomial evaluation $f(\beta)$ like a number written in base-$\beta$. Just as you can extract the digits of a base-10 number by looking at its magnitude, you can extract the sparse terms of $f(x)$ if $\beta$ outscales the maximum possible coefficient and the minimum difference between any two possible coefficients.
- Modular Arithmetic is a Scalpel: Classical Kronecker substitution is a sledgehammer that guarantees no term collisions but destroys efficiency by creating astronomically high degrees. By applying modular arithmetic to the exponents, the authors turn this sledgehammer into a scalpel—compressing the polynomial into a manageable size while preserving the distinct identity of its sparse terms.
Key Results
- Optimal Univariate Complexity: The univariate algorithm achieves a bit complexity of $\tilde{O}(td)$ (where $t$ is the number of terms and $d$ is the degree). The authors note this is likely the optimal bit complexity for any deterministic, exact black-box interpolation algorithm.
- Polynomial Multivariate Complexity: The probabilistic multivariate algorithm achieves a bit complexity of $\tilde{O}(n T^3 D \log H \log C)$ (where $n$ is variables, $T$ is terms, $D$ is degree, and $H, C$ are coefficient bounds). This proves the algorithm runs in polynomial time relative to the size of the inputs.
- Empirical Scaling: Experimental results in Maple confirm the theoretical math: the algorithm's runtime scales linearly with the number of terms ($T$) and degree ($D$), and logarithmically with the size bounds of the coefficients ($C$ and $H$).
Limitations and Future Work
- Requires Prior Bounds: A fundamental limitation of this approach is that it requires strict upper bounds to be known a priori. To use these algorithms, you must already know the maximum possible degree ($D$), the maximum number of terms ($T$), and the maximum absolute values of the coefficients and their denominators ($C$ and $H$).
- Future Applications: The authors note that this specific flavor of interpolation is highly motivated by the interpolation of sparse rational functions (fractions where the numerator and denominator are polynomials). The efficient algorithms presented here open the door to faster identity testing and recovery of complex multivariate rational functions in computer algebra systems.
Summary updated