Special Year in Computational Complexity Theory

Institute For Advanced Study, Princeton NJ

Investigators

Abstract

Avi Wigderson 9987077 This project will support three senior researchers to participate in a special year on computational complexity theory at the Institute for Advanced Studies. These researchers will attract the participation of other top researchers in computational complexity. Computational complexity theory has opened up one of the most exciting fields of scientific and mathematical research over the last 20 years, with dramatic achievements and fundamental understandings appearing at a high rate. One obvious explanation for the recent progress in this field is that this research is guided by a few clear and focused questions, deeply motivated on scientific, practical and philosophical grounds. The most central of these are: P=NP?, or more generally, are the many natural computational problems we can't solve really difficult? NP=coNP?, or more generally, what constitutes a difficult theorem to prove: P=BPP?, or more generally, does randomization really help efficient computation? BPP=QP?, or more generally, can quantum mechanics be efficiently simulated classically? Resolving any of these questions is clearly very long term goal, but each has stimulated the development of concepts, problems, proof techniques and results which start paving a path towards a possible resolution. But what really characterized the progress, and explained much of the successes so far, was the unveiling of many rich and beautiful connections between the sets of concepts and sub-problems each of these major questions gave rise to. There is little doubt that such connections are, and will be, the foundation for understanding the major questions of complexity theory. Indeed, these connections are what is making the complex world of computational complexity into a theory. The focus of this special year at the Institute will be to better understand these connections and their implications, to unify and extend them, and to look for new ones.