Recent Advances in Computational Complexity (06w5031)
Stephen Cook (University of Toronto)
Arvind Gupta (University of British Columbia)
Russell Impagliazzo (University of California, San Diego)
Valentine Kabanets (Simon Fraser University)
Madhu Sudan (Harvard University)
Avi Wigderson (Institute for Advanced Study)
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.