08w5094 Analytic Tools in Computational Complexity

Arriving Sunday, August 3 and departing Friday, August 8, 2008

Organizers: Paul Beame (University of Washington), Stephen Cook (University of Toronto), Russell Impagliazzo (University of California, San Diego), Valentine Kabanets (Simon Fraser University), Avi Wigderson (Institute for Advanced Study).

Confirmed Participants

Press Release: Analytic Tools in Computational Complexity

Information for Participants

Schedule (PDF file)

Mailing List

Final Report (PDF file)

Objectives

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 notion of Gowers uniformity (which was introduced by Gowers to give an analytic proof of Szemeredi's theorem on arithmetic progressions, and whose use can be viewed as ``generalized Fourier analysis") has also been recently employed in the context of Probabilistically Checkable Proofs and hardness of approximation. A new paradigm in computational complexity is beginning to emerge, which involves reducing high dimensional discrete problems that arise in the study of Boolean functions to high dimensional continuous problems and then applying analytic methods to the resulting continuous problems.

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 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.