ITR Medium Award: Computational Complexity Theory 2003

点击翻译按钮获取中文摘要

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.