ITR Medium Award: Computational Complexity Theory 2003

这个建议代表了一个雄心勃勃的研究和教育目标的结合，如下所述。我们建议的研究是关于计算复杂性理论的基本问题，特别关注它们之间的交叉相互作用。特别是，我们将集中在以下三个方面：随机性在计算中的作用。这包括伪随机性，概率算法的去随机化，随机类对象的显式构造，如扩展器和收缩器，以及它们在数据结构，算法，网络，代码等方面的应用。这包括理解自然逻辑，代数和组合证明系统的力量和局限性。它还包括将这些与理解优化问题的自然搜索启发式方法、自动定理证明以及自然攻击对P vs. NP问题的局限性联系起来。各种计算模型的能力和局限性。这包括布尔和算术电路、量子计算、分支程序和（经典和量子）通信复杂性。IAS的教育议程一般，特别是数学学院的理论计算机科学课程，正在把今天最聪明的新博士变成明天的科学领导者。这是由学校在该领域的长期和短期存在的topleaders的广泛计划，以及几个广泛和多样化的系列，在一个高度互动的环境中，除了从事研究之外，没有任何职责。我们注意到，我们在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.