Randomness and Parallelism in Algorithms

这个项目研究随机性和并行性的作用。 涉及随机算法行为的特定问题 输入包括散列、打包和分区算法。 与 关于并行计算，PI（与Megiddo和Ramachandran） 表明，每个约束有两个变量的线性规划（和 在目标函数中）在polylog空间中是可解的。 这个项目 调查它是否在NC（或可能在RNC）中，沿着 问题的变化，以及它们与问题的关系， 匹配. 同样在调查中的还有处理器的缩减 并行算法中的计数。 特别令人感兴趣的问题是， 如有向图中的寻路，以及特殊情况，如平面 图表。

This project investigates the role of randomness and parallelism. Specific problems involving the behavior of algorithms with random input include hashing, packing, and partitioning algorithms. With respect to parallel computation, the PI (with Megiddo and Ramachandran) showed that linear programming with two variables per constraint (and in the objective function) is solvable in polylog space. This project investigates whether it is in NC (or possibly RNC), along with variations of the problem, and their relation to problems such as matching. Also under investigation is the reduction of the processor count in parallel algorithms. Of particular interest are problems such as path-finding in directed graphs, and special cases such as planar graphs.