Revisit Sparse Polynomial Interpolation Based on Randomized Kronecker Substitution

Qiao-Long Huang, Xiao-Shan Gao

TL;DR

This paper introduces a novel Monte Carlo algorithm that efficiently interpolates sparse multivariate polynomials over finite fields. By reducing the problem to univariate interpolation and employing a refined Ben-Or and Tiwari algorithm, they achieve better or comparable complexities to existing methods, particularly for sparse polynomials.

What Problem Does This Paper Address?

Sparse polynomial interpolation is a fundamental problem in computer algebra. Given a black-box function that evaluates a polynomial, the goal is to find the polynomial itself. The challenge lies in the "black-box" nature (we don't know the polynomial's structure beforehand) and its "sparse" nature (it has many zero coefficients, meaning it has few terms). This is particularly tricky for multivariate polynomials over finite fields, where existing algorithms can be computationally expensive. The paper aims to improve the efficiency of these algorithms, especially for sparse polynomials, by developing a more effective reduction strategy.

Methods

The core of the paper's contribution lies in a two-pronged approach:

  1. Reduction to Univariate Interpolation: They propose a new Monte Carlo method that reduces the multivariate interpolation problem to a series of univariate interpolation problems. This is achieved using a "randomized Kronecker substitution," a technique that cleverly transforms the multivariate polynomial into a univariate one. The key is that this reduction is probabilistic and efficient.
  2. Modified Univariate Algorithm: They present an improved version of the Ben-Or and Tiwari algorithm for univariate polynomial interpolation over finite fields. This modified algorithm offers better complexity than the standard Lagrange interpolation method, especially when dealing with sparse polynomials.

By combining these two components, they construct a powerful multivariate interpolation algorithm.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and analysis, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Monte Carlo for Efficiency: The paper leverages a Monte Carlo approach, which uses randomness to achieve efficiency. This is crucial for handling the inherent uncertainty of black-box polynomial interpolation.
  • Kronecker Substitution as a Bridge: The randomized Kronecker substitution is a clever mathematical tool that bridges the gap between multivariate and univariate polynomial interpolation, making the problem more tractable.
  • Optimized Univariate Interpolation: Improving the univariate interpolation step is critical. The modified Ben-Or and Tiwari algorithm provides a significant speedup for this sub-problem, directly benefiting the overall multivariate algorithm.
  • Focus on Sparsity: The algorithms are specifically designed to exploit the sparsity of polynomials, which is a common characteristic in many practical applications.

Key Results

The paper presents a new Monte Carlo multivariate interpolation algorithm for black-box polynomials over finite fields. The key results are:

  • Improved Complexity: The proposed algorithm offers better or comparable complexities compared to existing reduction-based methods, especially for sparse polynomials.
  • Specific Complexity Bounds: For a polynomial with term bound $T$ and degree bound $D$, the algorithm achieves a bit complexity of $O~(nTD \log q + nTB_f)$, where $B_f$ is the cost of evaluating the black-box.
  • Finite Field Performance: When applied over finite fields, the algorithm requires $O~(nT)$ evaluations of the black-box and $O~(nTD \log q)$ bit operations. This is shown to be competitive with or superior to previous methods.

Limitations and Future Work

  • Monte Carlo Nature: The algorithm is probabilistic, meaning it might fail with a small probability. The paper provides bounds on this failure probability.
  • Quantum Algorithms: The paper briefly mentions that quantum algorithms could further improve the discrete logarithm problem solving step, leading to even faster interpolation for certain scenarios. This suggests a potential avenue for future research.
  • Practical Performance: While theoretical complexities are analyzed, the paper includes experimental results (Figures 1-3) that show the algorithm's performance aligns with theoretical predictions, suggesting practical viability. However, a more extensive empirical study across various polynomial structures and field sizes could be beneficial.

Summary updated

Abstract

In this paper, a new reduction based interpolation algorithm for general black-box multivariate polynomials over finite fields is given. The method is based on two main ingredients. A new Monte Carlo method is given to reduce the black-box multivariate polynomial interpolation problem to the black-box univariate polynomial interpolation problem over any ring. The reduction algorithm leads to multivariate interpolation algorithms with better or the same complexities in most cases when combining with various univariate interpolation algorithms. A modified univariate Ben-Or and Tiwari algorithm over the finite field is proposed, which has better total complexity than the Lagrange interpolation algorithm. Combining our reduction method and the modified univariate Ben-Or and Tiwari algorithm, we give a Monte Carlo multivariate interpolation algorithm, which has better total complexity in most cases for sparse interpolation of black-box polynomial over finite fields.
BibTeX
@inproceedings{huang2019revisit,
  author = {Qiao-Long Huang and Xiao-Shan Gao},
  title = {{Revisit Sparse Polynomial Interpolation Based on Randomized Kronecker Substitution}},
  booktitle = {CASC},
  year = {2019},
  doi = {10.1007/978-3-030-26831-2\_15},
}

Loading related content...

Figure