Reducing randomness via irrational numbers

Zhi Zhong Chen, Ming Yang Kao

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiency 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.

Original languageEnglish (US)
Pages (from-to)1247-1256
Number of pages10
JournalSIAM Journal on Computing
Volume29
Issue number4
DOIs
StatePublished - 2000

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

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

Cite this