Checking Polynomial Identities over any Field: Towards a Derandomization?

Daniel Lewin and Salil Vadhan

---

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 log(d_i+1) 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.

---

Versions

• Preliminary version, November 1997. (Has some proofs omitted from the proceedings version below.) [scanned pdf]
• In Proceedings of 30th Annual ACM Symposium on Theory of Computing, pp. 438-447, Dallas, TX, May 1998. ACM.
  [postscript][pdf][compressed postscript]
  

---

BibTeX entry

@InProceedings{LewinVa98,
  author =       {Daniel Lewin and Salil Vadhan},
  title =        {Checking Polynomial Identities over any Field: Towards a Derandomization?},
  booktitle =    "Proceedings of the 30th Annual ACM Symposium on
                  Theory of Computing",
  year =         "1998",
  organization = "ACM",
  address =      "Dallas, TX",
  month =        "May",
  pages =        "438--437"
}

---

[ back to Salil Vadhan's research interests ]