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.

该建议代表了下面介绍的雄心研究和教育目标的结合。我们提出的研究是关于计算复杂性理论的基本问题，并特别关注它们之间的交叉互动。特别是，我们将专注于以下三个领域。计算中随机性的力量。其中包括概率算法的范式化，诸如扩展器和提取器之类的随机对象的显式结构，以及它们在数据结构，算法，网络，代码，代码等中的应用。证明和搜索证明的复杂性。这包括了解自然逻辑，代数和组合证明系统的力量和限制。它还包括将这些关联与理解自然搜索启发式方法，以进行优化问题，自动化理论，以及对PS. NP问题的自然攻击的局限性。各种计算模型的功能和局限尤其是数学学院的科学课程，将今天的新鲜博士变成了明天的科学领导者。这是一项促进了该领域的永久性，长期和短期的广泛，长期和短期存在的计划。这两个目标的卓越成就记录。