CAREER: Randomized Computations and Probabilistically Checkable Proofs

职业：随机计算和概率可检查证明

• 批准号: 0406156
• 负责人: Luca Trevisan
• 金额: $ 8.39万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2004-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0406156&HistoricalAwards=false
• 关键词: CAREER; Randomized; Computations; Probabilistically; Checkable

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.

摘要：随机性的使用会以戏剧性且尚未完全理解的方式影响计算：在算法设计中，它产生了更简单，更有效的方法来解决计算问题；在复杂性理论中，它提出了有时会导致意外（和深远）结果的新概念和模型。这个职业发展项目涉及与计算随机性有关的研究和教育活动的集合。该项目的研究组成部分涉及两个主要主题。一个目标是开发一般工具，可用于使随机算法更强大，以便即使使用有偏见且有限的随机来源来实施它们，它们也可以工作。这样的工具是随机提取器，将偏置分布转换为几乎均匀的工具，以及伪随机发电机，这些过程将简短的随机输入扩展到更长的输出中，该输出具有无法区分的属性（具有精确的技术含义的术语）。研究组成部分的另一个主题是研究概率可检查的证明（PCP），这是一种计算模型，它在有效的随机证明检查方面具有令人惊讶的NP表征。 PCP模型是证明有关寻找NP-HARD组合优化问题的近似解决方案的复杂性的最佳工具。该项目的目的是在PCP模型中寻找更强的NP特征，以便更多地适用于研究优化问题的近似性，并特别强调NP的PCP表征的简化证明，该结果当前具有非常复杂的证明。该项目的材料将在现有的Algorishsmist和Proginals of Squesys中，并将其整合在pssemists上。关于算法和复杂性，并进入主要研究者正在发展的密码学课程。教育组成部分的主要目的是为迄今为止仅限于研究的研究生课程的一些结果提供基础演示。 这是不幸的，因为它们具有相关性和娱乐性，并不是特别难以解释，并且可以具有强烈的动机影响力。 该材料将开发大量的讲义。