DIMACS Princeton Theory Seminar
Title:
Reducing Randomness via Irrational Numbers
Speaker:
- Ming-Yang Kao
- Duke University
Place:
- Room 402, Computer Science Building
- 35 Olden Street
- Princeton University.
Time:
- 12:05 PM (Lunch will be served at 11:45 AM)
- Thursday, February 27, 1997 ** Note Change in Day **
Contact:
- Sanjeev Arora (arora@cs.princeton.edu)
Abstract:
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