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.