Can I read Reducing Randomness via Irrational Numbers on EtoBox?

Reducing Randomness via Irrational Numbers by Zhi-Zhong Chen; Ming-Yang Kao is a scholarly article available to read on EtoBox.

What is Reducing Randomness via Irrational Numbers about?

We propose a general methodology for testing whether a polynomial with integer coefficients is identically zero. The methodology is to evaluate the polynomial at suitable approximations of easily computable irrational points. An innovative feature of the methodology is that the error probability of the testing algorithm can be decreased by increasing the precision of the approximations of the chosen irrational numbers, instead of increasing the number of random bits as usual. To explain our methodology, we discuss the problem of deciding whether a graph has a perfect matching. Our new randomized NC algorithm uses fewer random bits without doing more work than all the previous randomized NC algorithms for the problem. We also apply the methodology to the problem of checking the equivalence of two multisets of integers. Our new randomized aJgorithm for this problem runs faster and uses fewer random bits than one of the two algorithms of Blum and Kannan. It also runs faster than the other for a large range of inputs on a more realistic model of computation than theirs.

Author

Zhi-Zhong Chen; Ming-Yang Kao

Publisher

ACM Press

Published

1997

Language

EN