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.