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 language||English (US)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - Jan 1 1997|
|Event||Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA|
Duration: May 4 1997 → May 6 1997
ASJC Scopus subject areas