ITR Medium Award: Computational Complexity Theory 2003

ITR 中奖：计算复杂性理论 2003

• 批准号: 0324906
• 负责人: Avi Wigderson
• 金额: $ 150万
• 依托单位: Institute For Advanced Study
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0324906&HistoricalAwards=false
• 关键词: ITR; Medium; Award; Computational; Complexity

This proposal represents a combination of ambitiousresearch and educational objectives, described below.The research we propose is on the fundamental problems ofcomputational complexity theory, with special focus on the crossinteractions between them. In particular, we will concentrate onthe following three areas.The power of randomness in computation. This includespseudorandomness, derandomization of probabilistic algorithms,explicit constructions of random-like objects such as expanders andextractors, and their applications in data structures,algorithms, networks, codes and more.The complexity of proofs and search for proofs. This includes understanding the powerand limitations of natural logical, algebraic and combinatorial proofsystems. It also includes relating these to understanding naturalsearch heuristics for optimization problems, to automated theoremproving, and to the limitations ofnatural attacks on the P vs. NP problem.The power and limitations of various computational models.This includes Boolean and arithmetic circuits, quantum computations,branching programs and (classical and quantum) communication complexity.The educational agenda of the IAS in general, and of the TheoreticalComputer Science program in the School of Mathematics in particular,is turning thebrightest fresh PhDs of today into scientific leaders of tomorrow.This is facilitated byan extensive program of permanent, long and short term presence of topleaders in the field at the school, together with severalextensive and diverse seminarseries, in a highly interactive environment with no duties exceptpursuing research.We note that our program at the IAS (partly with NSF support) has already a proven track record of excellence in both objectives.

该提案代表了雄心勃勃的研究和教育目标的结合，如下所述。我们提出的研究是关于计算复杂性理论的基本问题，特别关注它们之间的交叉相互作用。我们将特别关注以下三个领域： 计算中随机性的力量。这包括伪随机性、概率算法的去随机化、类似随机对象（例如扩展器和提取器）的显式构造，以及它们在数据结构、算法、网络、代码等中的应用。证明和搜索证明的复杂性。这包括理解自然逻辑、代数和组合证明系统的力量和局限性。它还包括将这些与理解优化问题的自然搜索启发法、自动化理论改进以及 P 与 NP 问题的自然攻击的局限性联系起来。各种计算模型的力量和局限性。这包括布尔和算术电路、量子计算、分支程序和（经典和量子）通信复杂性。 IAS 的教育议程，特别是数学学院的理论计算机科学计划，正在使最聪明的人焕然一新。今天的博士成为明天的科学领袖。这是通过学校该领域的顶尖领导者的永久、长期和短期存在的广泛计划以及几个广泛和多样化的研讨会系列来促进的，在一个高度互动的环境中，除了追求研究之外没有任何职责。我们注意到，我们在 IAS 的项目（部分得到 NSF 的支持）已经在这两个目标方面取得了卓越的记录。