Analytic Tools in Computational Complexity (08w5094)


(University of Washington)

(University of Toronto)

(University of California San Diego)

Valentine Kabanets (Simon Fraser University)

(Institute for Advanced Study)


Computational complexity emerged from the combination of logic, combinatorics, information theory, and operations research. It coalesced around the central problem of "P versus NP" (one of the seven open problems of the Clay Institute). While this problem remains open, the field has grown both in scope and sophistication. An important development in the study of computational complexity has been increased role of analytic methods. Fourier analysis has become an essential tool of the field, playing a critical role in the study
of interactive proofs, the computational hardness of approximation problems, and the learnability of Boolean functions.

The objective of the workshop, which is to be held at the Banff International Research Station on August 3 - 8, 2008, 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 analytic tools used in a number of recent results in computational complexity, and to understand the power and limitations of such methods. The current research in computational complexity is characterized by a high degree of interpenetration of ideas from different fields of computer science and mathematics (e.g., coding theory, information theory, bounded arithmetic, and number theory). The use of analytic tools has already been quite fruitful for computational complexity, and one of the goals
of the proposed workshop is to strengthen the existing connections between analysis and computational complexity.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnologí­a (CONACYT).