Reducing randomness via irrational numbers
Reducing randomness via irrational numbers
复制标题
通过无理数减少随机性
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
M. Kao
中科院分区：
文献类型：
--
作者：
Zhi;M. Kao
我们提出了一种检验给定整数系数多项式是否为同零的一般方法。该方法在适当的无理点的可有效逼近处对多项式进行评估。与DeMillo， Lipton， Schwartz和Zippel的经典技术相比，这种方法可以通过提高近似的精度而不是使用更多的随机比特来降低错误概率。因此，使用经典技术的随机算法通常可以使用新方法进行改进。为了演示该方法，我们将讨论两个重要的应用程序。首先是判断一个图在并行中是否有完美匹配。我们的新NC算法比Chari， Rohatgi和Srinivasan之前最好的NC算法使用更少的随机位，同时做更少的工作。第二个应用是测试两个整数多集的相等性。我们的新算法改进了Blum和Kannan之前最好的算法，并且可以加快他们在大范围输入的排序程序的检查算法。
We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently com- putable 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 algo- rithms 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.