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

一个计算问题的解的数量及其分布对其计算效率有着根本的影响。当解是对称定位时，不能区分两个解的算法不能（通过对称）收敛到任何一个答案。随机化通常是有效的，因为它可以打破这种对称性。在联合工作中，PI已经证明了随机性的敌对源足以破坏对称性（因此表明RP = SRP）。这种方法的新颖之处在于，将对称性破缺确定为随机化的基本任务，使人们能够更精确地询问高效计算到底需要多少随机性。现在要解决的两个相关问题是：随机性来源成为普遍对称性破坏者的充分必要条件是什么？需要多少个随机比特？如果一个伪随机数生成器的输出满足普适对称性破缺的性质，那么它就是准完美的。PI最近提出了一个简单高效的伪随机数生成器。现在正在尝试解决相关的猜想，即这个生成器是准完美的。大规模并行计算提供了另一种情况，其中的困难可能在于从许多解决方案中选择一个解决方案。在联合工作中，PI给出了并行隔离一个解的一般方案（获得了最大匹配问题的并行算法）。目前正在探索这种隔离方案的进一步应用。他被总统青年调查团评为“杰出的计算机科学家”。

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.