ITR Medium Award: Computational Complexity Theory 2003

Institute For Advanced Study, Princeton NJ

Investigators

Abstract

This proposal represents a combination of ambitious research and educational objectives, described below. The research we propose is on the fundamental problems of computational complexity theory, with special focus on the cross interactions between them. In particular, we will concentrate on the following three areas. The power of randomness in computation. This includes pseudorandomness, derandomization of probabilistic algorithms, explicit constructions of random-like objects such as expanders and extractors, and their applications in data structures, algorithms, networks, codes and more. The complexity of proofs and search for proofs. This includes understanding the power and limitations of natural logical, algebraic and combinatorial proof systems. It also includes relating these to understanding natural search heuristics for optimization problems, to automated theorem proving, and to the limitations of natural 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 Theoretical Computer Science program in the School of Mathematics in particular, is turning the brightest fresh PhDs of today into scientific leaders of tomorrow. This is facilitated by an extensive program of permanent, long and short term presence of top leaders in the field at the school, together with several extensive and diverse seminar series, in a highly interactive environment with no duties except pursuing research. We note that our program at the IAS (partly with NSF support) has already a proven track record of excellence in both objectives.