Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-018 | 8th June 1999 00:00

Reducing Randomness via Chinese Remaindering

RSS-Feed




TR99-018
Authors: Manindra Agrawal, Somenath Biswas
Publication: 8th June 1999 17:56
Downloads: 3517
Keywords: 


Abstract:


We give new randomized algorithms for testing multivariate polynomial
identities over finite fields and rationals. The algorithms use
\lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil
in case of rationals where C is the largest coefficient)
random bits to test if a
polynomial P(x_1, ..., x_n) is zero where d_i is the degree of
x_i in P and has an error probability of \epsilon for any
\epsilon > 0. The running time of the algorithms is polynomial in
the size of arithmetic circuit representing the input polynomial and
1/\epsilon.
These algorithms use fewer random bits than all the known methods and
also take an order of magnitude less time compared to
some of the recently proposed methods [Chen-Kao, Lewin-Vadhan].
Our algorithms first transform the input polynomial to a univariate
polynomial and then uses Chinese remaindering over univariate
polynomials to efficiently test if it is zero.

We also give a simple test for primality based on identity
checking.



ISSN 1433-8092 | Imprint