DIMACS Princeton Theory Seminar


Reducing Randomness via Irrational Numbers


Ming-Yang Kao
Duke University


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:05 PM (Lunch will be served at 11:45 AM)
Thursday, February 27, 1997 ** Note Change in Day **


Sanjeev Arora (arora@cs.princeton.edu)


We propose a general methodology for testing whether a given 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 given 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 given 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.

(joint work with Z. Z. Chen)

Document last modified on February 20, 1997