Checking Polynomial Identities over any Field: Towards a Derandomization?

DSpace/Manakin Repository

Checking Polynomial Identities over any Field: Towards a Derandomization?

Citable link to this page

 

 
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:
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:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters