基于Kronecker型替换的黑盒多项式稀疏插值

本文基于新的Kronecker型替换,给出两个由黑盒表示的稀疏多项式的新确定性插值算法.令f∈Rx1,……,xn]是一个稀疏黑盒多项式,其次数上界为D.当R是C或者是有限域时,相对于已有算法,新算法具有更好的计算复杂度或者关于D的复杂度更低.特别地,对于一般黑盒模型,D是复杂度中的主要因素,而在所有的确定性算法中,本文的第二个算法的复杂度关于D是最低的.

Deterministic sparse interpolation of black-box multivariate polynomials using Kronecker type substitutions

In this paper, we propose two new deterministic interpolation algorithms for a sparse multivariate polynomial given as a standard black-box by introducing new Kronecker type substitutions. Let f ∈ Rx1,..., xn]be a sparse black-box polynomial with a degree bound D. When R equals C or a finite field, our algorithms either have better bit complexity or better bit complexity in D than existing deterministic algorithms. In particular,in the case of deterministic algorithms for standard black-box models, our second algorithm has the current best complexity in D which is the dominant factor in the complexity.