CAREER: Randomized Computations and Probabilistically Checkable Proofs

摘要：随机性的使用以一种戏剧性的、尚未完全理解的方式影响着计算：在算法设计中，它产生了更简单、更有效的方法来解决计算问题；在复杂性理论中，它提出了新的概念和模型，有时会导致意想不到的（和深远的）结果。这个职业发展项目涉及与计算随机性相关的一系列研究和教育活动。这个项目的研究部分涉及两个主要主题。一个目标是开发通用工具，使随机算法更加健壮，这样即使它们是使用有偏差的、有限的随机性来源来实现的，它们也能工作。这些工具是随机提取器，将有偏差的分布转换为几乎均匀的分布的过程，以及伪随机生成器，将短的随机输入扩展为具有与均匀分布不可区分（具有精确技术含义的术语）的更长的输出的过程。研究部分的另一个主题是概率可检验证明（PCP）的研究，这是一种计算模型，它在有效的随机证明检验方面给出了NP的惊人特征。PCP模型是证明NP-hard组合优化问题的近似解的复杂性的最著名的工具。这个项目的目标是在PCP模型中寻找更强的NP特征，以便更多地应用于优化问题的近似性研究，并特别强调对NP的PCP特征的简化证明，这一结果目前具有极其复杂的证明。该项目的教育部分将把随机算法、伪随机和概率证明系统的材料整合到现有的算法和复杂性课程中，以及首席研究员正在开发的一门关于密码学的新课程中。教育部分的一个主要目标是对迄今为止仅限于研究型研究生课程的一些成果进行初步介绍。这是不幸的，因为它们是相关的和有趣的，不是特别难以解释，可以有很强的激励影响。将根据这些材料制作一套广泛的课堂讲稿。

Summary:The use of randomness affects computations in dramatic and not yet fully understood ways: in algorithm design it yields simpler and more efficient ways to solve computational problems; in complexity theory it suggests new concepts and models that lead sometimes to unexpected (and far-reaching) results. This career development project involves a collection of research and educational activities related to computational randomness.The research component of this project deals with two main themes. One goal is the development of general tools that can be used to make randomized algorithms more robust, so that they can work even if they are implemented using biased, and limited, sources of randomness. Such tools are randomness extractors, procedures that convert biased distributions into almost uniform ones, and pseudorandom generators, procedures that stretch a short random input into a much longer output that has the property of being indistinguishable (a term that is given a precise technical meaning) from the uniformdistribution. The other theme of the research component is the study of probabilistically checkable proofs (PCP), a model of computation that gives a surprising characterization of NP in terms of efficient randomized proof-checking. The PCP model is the best known tool to prove results about the complexity of finding approximate solutions for NP-hard combinatorial optimization problems. The goal of this project is to look for stronger characterizations of NP in the PCP model, for more applications to the study of the approximability of optimization problems and, with special emphasis, for a simplified proof of the PCP characterization of NP, a result that currently has an exceedingly complicated proof.The educational component of this project will integrate material on randomized algorithms, pseudorandomness, and probabilistic proof-systems into existing courses on algorithms and complexity and into a new course on cryptography that the principal investigator is developing. A main goal of the educational component is to give elementary presentations of some results that have so far been confined to research-oriented graduate courses. This is unfortunate because they are relevant and entertaining, not particularly hard to explain, and can have a strong motivational influence. An extensive set of lecture notes will be developed on this material.