TL;DR
This paper introduces new deterministic and Monte Carlo algorithms for interpolating sparse multivariate polynomials represented by straight-line programs (SLPs). These algorithms offer improved computational complexity, particularly for sparse polynomials, and are the first to achieve linear complexity in the number of variables and terms for Monte Carlo methods.
What Problem Does This Paper Address?
Interpolating polynomials is a fundamental problem in computer algebra. When dealing with sparse multivariate polynomials (polynomials with many variables but few non-zero terms), efficiently reconstructing the polynomial from its values or a representation is crucial. This paper focuses on a specific representation: straight-line programs (SLPs), which are sequences of arithmetic operations that define a polynomial. Existing interpolation algorithms for SLPs often have complexities that are too high, especially for polynomials that are sparse (have a small term bound $T$) but can have a high degree bound $D$ or a large number of variables $n$. The challenge is to develop algorithms that are faster and more efficient, particularly for these sparse cases, and to do so over general computable rings and finite fields.
Methods
The authors propose several novel techniques:
- A Criterion for Term Testing: A key contribution is a method to deterministically check if a specific term belongs to a polynomial represented by an SLP. This is crucial for identifying and isolating terms during the interpolation process.
- Deterministic "Ok" Prime Finding: They provide a deterministic method to find an "ok" prime $p$. An "ok" prime is one where at least half of the polynomial's terms do not "collide" or merge when the polynomial is evaluated modulo $x^D - 1$ (a specific transformation). This is a significant improvement over probabilistic methods for finding such primes.
- New Kronecker-Type Substitution: A novel substitution is introduced to reduce multivariate polynomial interpolation to univariate interpolation. This substitution is designed to be deterministic and avoids increasing the data size significantly, unlike some previous methods.
- Deterministic and Monte Carlo Algorithms: Based on these techniques, they develop both deterministic and Monte Carlo algorithms. The deterministic algorithm has a complexity that is quadratic in $n$ and $T$, and cubic in $\log D$. The Monte Carlo algorithms offer even better complexities, achieving linearity in $n$ and $T$ in the "soft-Oh" sense, making them optimal for sparse polynomials.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithms and their complexity analysis, with experimental results presented in Section 7.
Key Insights and Ideas
- The Power of "Ok" Primes: The concept of an "ok" prime is central. By finding primes where terms are less likely to collide, the problem can be simplified, allowing for more efficient term identification. The deterministic method for finding such primes is a significant theoretical advancement.
- Reducing Multivariate to Univariate: The core strategy of reducing the multivariate problem to a univariate one via substitutions is a standard technique. However, the authors' new Kronecker-type substitution is designed to be more efficient and deterministic, offering a practical advantage.
- Term Testing as a Building Block: The ability to deterministically test if a term belongs to a polynomial is a fundamental building block. This allows for a more controlled and efficient process of reconstructing the polynomial term by term.
- Optimality for Sparse Polynomials: The Monte Carlo algorithms achieving linear complexity in $n$ and $T$ is a major breakthrough. This means their performance scales very well with the number of variables and terms, which is ideal for sparse polynomials.
Key Results
- Deterministic Algorithm: Achieves a complexity of $O~(Ln^2T^2 \log^2 D + LnT \log^3 D)$ arithmetic operations, which is better than existing deterministic algorithms for most sparse cases.
- Monte Carlo Algorithms:
- The first algorithm has a complexity of $O~(LnT(\log^3 D + \log D \log \mu))$ arithmetic operations with probability at least $1-\mu$.
- The second algorithm (over finite fields) has a bit complexity of $O~(LnT \log^2 D(\log D + \log q) \log \frac{1}{\mu})$ with probability at least $1-\mu$.
- These Monte Carlo algorithms are the first to achieve linear complexity in $n$ and $T$ (in the "soft-Oh" sense), making them optimal for sparse polynomials.
- Experimental Validation: Section 7 presents experimental results showing that the algorithms' practical performance aligns with their theoretical complexity bounds, demonstrating their effectiveness.
Limitations and Future Work
- Soft-Oh Notation: The complexity is expressed using "soft-Oh" notation ($O~$), which hides polylogarithmic factors. While this highlights the dominant terms, the actual performance can be affected by these hidden factors, as noted in the experimental results.
- Probabilistic Nature: The Monte Carlo algorithms provide a probabilistic guarantee of correctness. While the probability of error can be made arbitrarily small, it's not deterministic.
- Future Work: The paper lays the groundwork for further improvements, particularly in exploring more efficient algorithms for finite fields and potentially refining the deterministic algorithms. The experimental section suggests that while theoretical complexities are met, practical performance can still be influenced by factors not fully captured by the soft-Oh notation.
Summary updated