White-box sparse interpolation

Question

Let $C$ be an arithmetic circuit that represents a polynomial $f\in\mathbb K[x_1,\dotsc,x_n]$, with the promise that $f$ has at most $k$ nonzero terms. What is (known about) the complexity of computing $f$ in its sparse representation, given $C$?

I am interested in deterministic and randomized complexity, and in the link with PIT. In particular, does the promise that $f$ is sparse imply good algorithms? A priori, I am more interested in the case of $\mathbb K$ being some finite field, though results over other fields may be relevant.

Answer 1

There are deterministic and randomized algorithm running in time $\mathrm{poly}(n,d,k)$, where $n$ is the number of variables, $d$ is the degree and $k$ is the sparsity. AFAIK, the results are stated for characteristic zero fields but work over any field large enough (again, polynomially large in the parameters).

This paper of Kaltofen and Yagati discusses both the randomized algorithm of Zippel and the deterministic algorithm of Ben-Or and Tiwari, and then goes on to present some improvements.

Answer 2

There are deterministic algorithms that can do it even in time polynomial in $n$, $k$, $\log d$, and $L$ ($n$ numbers of variables, $k$ sparsity, and $d$ the degree, $L$ the bit length of the coefficients), see e.g. Garg and Schost, Interpolation of polynomials given by straight-line programs. Theor. Comput. Sci. 410(27-29): 2659-2662 (2009) or Bläser and Jindal, A new deterministic algorithm for sparse multivariate polynomial interpolation. ISSAC 2014: 51-58. The first algorithms should even work over arbitrary rings.