ITR Medium Award: Computational Complexity Theory 2003

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

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.