10
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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" 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.