<p>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.</p>

CC BY-SA 3.0
2017-07-13T09:53:09.290Z
2017-07-13T09:53:09.290Z
Markus Bläser
<p>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). </p>

<p><a href="http://www4.ncsu.edu/~kaltofen/bibliography/88/KaLa88.pdf" rel="noreferrer">This paper of Kaltofen and Yagati</a> discusses both the <a href="http://www.sciencedirect.com/science/article/pii/S0747717108800181" rel="noreferrer">randomized algorithm of Zippel</a> and the <a href="http://dl.acm.org/citation.cfm?id=62241" rel="noreferrer">deterministic algorithm of Ben-Or and Tiwari</a>, and then goes on to present some improvements. </p>

CC BY-SA 3.0
2017-07-11T12:06:10.030Z
2017-07-11T12:06:10.030Z
Ramprasad
<p>Let $C$ be an <a href="https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity" rel="noreferrer">arithmetic circuit</a> 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$?</p>

<p>I am interested in deterministic and randomized complexity, and in the link with <a href="https://en.wikipedia.org/wiki/Polynomial_identity_testing" rel="noreferrer">PIT</a>. In particular, does the promise that $f$ is sparse imply good algorithms? <em>A priori</em>, I am more interested in the case of $\mathbb K$ being some finite field, though results over other fields may be relevant.</p>

<arithmetic-circuits>
White-box sparse interpolation
Bruno
# White-box sparse interpolation

(Asked by: username_0 on 2017-07-11)

Let $C$ be an [arithmetic circuit](https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity) 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](https://en.wikipedia.org/wiki/Polynomial_identity_testing). 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.

**Tags:** arithmetic-circuits

---

## 2 answers

### Answer by username_1 on 2017-07-13. Score: 6

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.


---

### Answer by username_2 on 2017-07-11. Score: 6

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](http://www4.ncsu.edu/~kaltofen/bibliography/88/KaLa88.pdf) discusses both the [randomized algorithm of Zippel](http://www.sciencedirect.com/science/article/pii/S0747717108800181) and the [deterministic algorithm of Ben-Or and Tiwari](http://dl.acm.org/citation.cfm?id=62241), and then goes on to present some improvements.


---

