<p>Not really what you asked for, but your question was a bit open, so maybe this will interest you.</p>

<p>For the specific problem of estimating infinite polynomials (generating functions), $A(z) = \sum_{n=0}^\infty a_n z^n$, with a combinatorial origin, there is a recently published paper, "<a href="http://www.sciencedirect.com/science/article/pii/S0097316512000908" rel="nofollow">Algorithms for combinatorial structures: Well-founded systems and Newton iterations</a>" by Pivoteau, Salvy and Soria. I believe (though I might be slightly off) it shows that approximations can be computed in complexity that is quadratic in the required precision. The set of points is the radius of convergence, and in particular the singularity of the generating function.</p>

CC BY-SA 3.0
2012-07-02T16:35:12.490Z
2012-07-02T16:35:12.490Z
Jérémie
<p>There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero.  Are there any results of algorithms that do some sort of estimation of polynomials over a specific set of points? This could be, for instance, approximating for what fraction of these points the polynomial evaluates to zero, or approximating the average value of the polynomial over these points?  The set of points can be specific to the algorithm.</p>

<ds.algorithms><approximation-algorithms><randomized-algorithms><derandomization><polynomials>
What are some results on algorithms that estimate polynomials over a given set of points?
Shravas Rao
# What are some results on algorithms that estimate polynomials over a given set of points?

(Asked by: username_0 on 2012-06-29)

There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero. Are there any results of algorithms that do some sort of estimation of polynomials over a specific set of points? This could be, for instance, approximating for what fraction of these points the polynomial evaluates to zero, or approximating the average value of the polynomial over these points? The set of points can be specific to the algorithm.

**Tags:** ds.algorithms, approximation-algorithms, randomized-algorithms, derandomization, polynomials


---

## 1 answers

### Answer by username_1 on 2012-07-02. Score: 2

Not really what you asked for, but your question was a bit open, so maybe this will interest you.

For the specific problem of estimating infinite polynomials (generating functions), $A(z) = \sum\_{n=0}^\infty a\_n z^n$, with a combinatorial origin, there is a recently published paper, "[Algorithms for combinatorial structures: Well-founded systems and Newton iterations](http://www.sciencedirect.com/science/article/pii/S0097316512000908)" by Pivoteau, Salvy and Soria. I believe (though I might be slightly off) it shows that approximations can be computed in complexity that is quadratic in the required precision. The set of points is the radius of convergence, and in particular the singularity of the generating function.


---

