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.
%0 Generic
%1 citeulike:191057
%A Chen, Zhi-Zhong
%A Kao, Ming-Yang
%D 2000
%K irrational
%T Reducing Randomness via Irrational Numbers
%U http://arxiv.org/abs/cs.DS/9907011
%X 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.
@misc{citeulike:191057,
abstract = {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.},
added-at = {2007-08-18T13:22:24.000+0200},
author = {Chen, Zhi-Zhong and Kao, Ming-Yang},
biburl = {https://www.bibsonomy.org/bibtex/21504c1c59cb6bd4c5478101b9e5f5dcd/a_olympia},
citeulike-article-id = {191057},
description = {citeulike},
eprint = {cs.DS/9907011},
interhash = {2070fcb7cfeb564f052c222c97542607},
intrahash = {1504c1c59cb6bd4c5478101b9e5f5dcd},
keywords = {irrational},
month = {November},
priority = {2},
timestamp = {2007-08-18T13:22:50.000+0200},
title = {Reducing Randomness via Irrational Numbers},
url = {http://arxiv.org/abs/cs.DS/9907011},
year = 2000
}