Organizers: Valentine Kabanets (Simon Fraser University), Stephen Cook (University of Toronto), Arvind Gupta (Simon Fraser University), Russell Impagliazzo (University of California, San Diego), Madhu Sudan (M.I.T.), Avi Wigderson (Institute for Advanced Study, Princeton).
Computational Complexity Theory is the field that studies the efficiency of computation. Its major goals are to find efficient algorithms for natural problems in natural computational models, or to show that no efficient solutions exist. The famed "P versus NP" problem (one of the seven open problems of the Clay Institute) is the central problem of this field and, despite three decades of active research, this problem has eluded resolution. However, during this period, our understanding of efficient computation has improved significantly through a number of concepts, techniques and results, including:
- Discovery of efficient ways of converting computational hardness into computational randomness (hardness-randomness tradeoffs), and other techniques for eliminating or reducing randomness use in probabilistic algorithms.
- Classification of hardness of approximation algorithms for a number of optimization problems, using the concept of Probabilistically Checkable Proofs (PCP).
- Connections of both items above to old and new problems in coding and information theory, which fertilized both fields.
- Investigations of the complexity of proofs, and their connections to limits on circuit lower bounds on the one hand, and to the complexity of search heuristics on the other.
- Use of quantum computation to get efficient algorithms for classically difficult problems (such as factoring), as well as using quantum arguments to obtain complexity results in the classical model of computation.
The goal of this workshop is to examine these and other recent achievements in complexity theory, exchange ideas, formulate open problems, and identify new directions of research.