Reducing randomness via irrational numbers

Zhi Zhong Chen*, Ming Yang Kao

*Corresponding author for this work

Research output: Contribution to journalConference article

27 Scopus citations

Abstract

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 algorithm 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.

Original languageEnglish (US)
Pages (from-to)200-209
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Jan 1 1997
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Reducing randomness via irrational numbers'. Together they form a unique fingerprint.

  • Cite this