Presidential Young Investigator Award: Randomness and Parallelism in the Solution of Computational Problems

点击翻译按钮获取中文摘要

The number of solutions of a computational problem and their distribution have fundamental implications upon its computational efficiency. When the solutions are symmetrically located an algorithm that cannot distinguish between two solutions cannot (by symmetry) converge to either answer. Randomization is often effective precisely because it can break such symmetries. In joint work, the PI has shown that an adversary source of randomness is sufficient to break symmetries (thus showing RP = SRP). What is novel about this approach is that identifying symmetry breaking as the essential task of randomization allows one to ask more precisely how much randomness is really needed for efficient computation. Two related questions now being addressed are: What are necessary and sufficient conditions for a source of randomness to be a universal symmetry breaker? How many random bits are necessary? A pseudo-random number generator is quasi-perfect if its output satisfies universal symmetry breaking properties. The PI has recently proposed a simple and efficient pseudo-random number generator. An attempt is now being made to settle the associated conjecture that this generator is quasi-perfect. Massively parallel computation provides another context where the difficulty can lie in the task of selecting one solution among many. In joint work the PI has given a general scheme for isolating one solution in parallel (obtaining a parallel algorithm for the maximum matching problem). Further applications of this isolating scheme are now being explored. The PI has been judged to be an outstanding computer scientist by the Presidential Young Investigators panel.