06w5031 Recent Advances in Computational Complexity

Arriving Saturday, August 26 and departing Thursday, August 31, 2006

Organizers: 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).

Confirmed Participants

Information for Participants

Final Report (PDF file)

Objectives

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.