๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Zero testing of algebraic functions

โœ Scribed by Richard Zippel

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
427 KB
Volume
61
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 & that represents an algebraic function cy and a few additional parameters about (Y, we show how to test if (Y is equal to the zero function. @ 1997 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

Decomposition of Algebraic Functions
Decomposition of Algebraic Functions
โœ Dexter Kozen; Susan Landau; Richard Zippel ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 554 KB

Functional decomposition-whether a function f (x) can be written as a composition of functions g(h(x)) in a non-trivial way-is an important primitive in symbolic computation systems. The problem of univariate polynomial decomposition was shown to have an efficient solution by Kozen and Landau (1989)