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.
