Randomized Parallel Algorithms

虽然随机化在算法设计中的作用还没有被完全理解，但一些重要的计算问题已经用随机化优雅地解决了。对于各种问题，最著名的随机算法比它们的确定性对应物具有更好的资源边界。这个持续的研究项目通过研究随机化在几个计算问题的并行算法设计中的功能，解决了更好地理解随机化的问题，包括(1)排序和选择，(2)分组路由和(3)计算几何领域的问题。这些采样和算法工具在自然语言处理、计算机模拟和运动规划等不同领域的最优（或接近最优）并行算法设计中的应用也进行了研究。

While the role of randomization in algorithm design has not been fully understood, several important computational problems have been solved elegantly using randomization. The best known randomized algorithms for a variety of problems have better resource bounds than their deterministic counterparts. This continuing research project addresses the issue of better understanding randomization, by studying its function in the design of parallel algorithms for several computing problems, including those in the areas of (1) sorting and selection, (2) packet routing, and (3) computational geometry. Applications of these sampling and algorithmic tools to the design of optimal (or near optimal) parallel algorithms in such diverse areas as natural language processing, computer simulation, and motion planning, are also examined.