Algorithms for computing sparse shifts for multivariate polynomials

In this paper, we investigate the problem of finding t-sparse shifts for multivariate polynomials. Given a polynomial f is an element of F {[}x(1), x(2),..., x(n)] of degree d, and a positive integer t, we consider the problem of representing f(x) as a H-linear combination of the power products of u(i) where u(i) = x(i) - b(i) for some b(i) is an element of H, an extension of F, for i = 1,..., n, i.e., f = Sigma(j) F(j)u(alpha j), in which nt most t of the F-j are non-zero. We provide sufficient conditions for uniqueness of sparse shifts for multivariate polynomials, prove tight bounds on the degree of the polynomial being interpolated in terms of the sparsity bound t and a bound on the size of the coefficients of the polynomial in the standard representation, and describe two new efficient algorithms for computing sparse shifts for a multivariate polynomial.