Zero testing of algebraic functions
Richard E. Zippel · Information Processing Letters · 1997
It is well known that we can efficiently test whether a polynomial is identically zero or not by examining the values of the polynomial at well-chosen points. Both deterministic and efficient probabilistic algorithms have been devised for this purpose. It is not so well recognized that algebraic functions can be similarly tested for zeroness. The need for zero testing black boxes representing algebraic functions has recently arisen in the area of self-testing/self-correcting programs. Given a black box Bα that represents an algebraic function α and a few additional parameters about α, we show how to test if α is equal to the zero function.