Reducing Randomness via Irrational Numbers

Details Reducing Randomness via Irrational Numbers Reducing Randomness via Irrational Numbers

1999-07-07

arxiv.org/abs/cs/9907011v2

SIAM Journal on Computing, 29(4):1247--1256, 2000

Computer Science

Data Structures and Algorithms

Scientific paper

We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points. In contrast to the classical technique of DeMillo, Lipton, Schwartz, and Zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits. Consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology. To demonstrate the methodology, we discuss two nontrivial applications. The first is to decide whether a graph has a perfect matching in parallel. Our new NC algorithm uses fewer random bits while doing less work than the previously best NC algorithm by Chari, Rohatgi, and Srinivasan. The second application is to test the equality of two multisets of integers. Our new algorithm improves upon the previously best algorithms by Blum and Kannan and can speed up their checking algorithm for sorting programs on a large range of inputs.

Affiliated with

Also associated with

No associations

Rating

Reducing Randomness via Irrational Numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reducing Randomness via Irrational Numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing Randomness via Irrational Numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-531958