Analytic Tools in Computational Complexity (08w5094)

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.