# Checking Polynomial Identities over any Field: Towards a Derandomization?

 Title: Checking Polynomial Identities over any Field: Towards a Derandomization? Author: Lewin, Daniel; Vadhan, Salil P. Note: Order does not necessarily reflect citation order of authors. Citation: Lewin, Daniel and Salil Vadhan. 1998. Checking polynomial identities over any field: Towards a derandomization? In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC '98), May, Dallas, TX, 438-437. Association of Computing Machinery. Full Text & Related Files: Vadhan_PolyIdentityDerandom.pdf (181.6Kb; PDF) Abstract: We present a Monte Carlo algorithm for testing multivariate polynomial identities over any field using fewer random bits than other methods. To test if a polynomial $$P(x_1, ..., x_n)$$ is zero, our method uses $$\sum_{i=1}^n \log \lceil d_i+1 \rceil$$ random bits, where $$d_i$$ is the degree of $$x_i$$ in $$P$$, to obtain any inverse polynomial error in polynomial time. The algorithm applies to polynomials given as a black box or in some implicit representation such as a straight-line program. Our method works by evaluating P at truncated formal power series representing square roots of irreducible polynomials over the field. This approach is similar to that of Chen and Kao (STOC '97), but with the advantage that the techniques are purely algebraic and apply to any field. We also prove a lower bound showing that the number of random bits used by our algorithm is essentially optimal in the black-box model. Published Version: doi:10.1145/276698.276856 Other Sources: http://people.seas.harvard.edu/~salil/research/polys.pdf Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:11130439 Downloads of this work: