Recent Advances in Computational Complexity (06w5031)
Stephen Cook (University of Toronto)
Arvind Gupta (Mitacs)
Russell Impagliazzo (University of California, San Diego)
Valentine Kabanets (Simon Fraser University)
Madhu Sudan (Microsoft Research)
Avi Wigderson (Institute for Advanced Study)
The objective of the workshop is to bring together some of the most active researchers in computational complexity as well as a few senior graduate students and postdocs to examine the recent progress in the field, formulate open problems, and identify new directions of research.
A salient feature of the current research in computational complexity is the interpenetration of ideas from different fields of computer science and mathematics: coding theory, information theory, bounded arithmetic, and number theory, to name just a few. Some of the most exciting recent developments in theoretical computer science were the result of such exchange of ideas. (For example, an elementary combinatorial construction of constant-degree expander graphs due to Reingold, Vadhan, and Wigderson came as a result of applying the information-theoretic techniques developed in the study of randomness extractors.) By bringing together the computer scientists working in logic, coding theory, computational randomness, and quantum computing, we aim to ensure that such fruitful interaction among different research areas of computational complexity will continue.