Computational Complexity (13w5010)

Arriving in Banff, Alberta Sunday, July 7 and departing Friday July 12, 2013


(University of Washington)

(University of California, San Diego)

(Simon Fraser University)

(University of Toronto)

(Institute for Advanced Study)


Complexity theory has often been using (and contributing to) a number
of different areas of mathematics: logic, combinatorics, algebra,
geometry, and analysis, to name just a few. For example,
mathematicians Lubotzky, Phillips, and Sarnak used some deep results
in group theory to construct an explicit family of expander graphs. A
completely elementary, combinatorial, explicit construction of
expander graphs has been later found by complexity theorists Reingold,
Vadhan, and Wigderson. The finite-field version of the famous Kakeya
conjecture has recently been solved by another complexity theorist,
Zeev Dvir, and then used for an explicit construction of randomness
extractors, combinatorial objects with many applications in complexity
theory. Also an important connection has been discovered between the
notions of pseudorandomness in mathematics, e.g., the Dense Model
Theorem of Green and Tao, and in complexity theory, e.g.,
Impagliazzo's Hardcore Lemma; this connection was used by Reingold,
Trevisan, Tulsiani, Vadhan, and Impagliazzo to derive a number of weak
regularity theorems in graph theory from the appropriate versions of
the Dense Model Theorem. Finally, an approach to the "P vs NP" problem
based on the tools from algebraic geometry ("geometric complexity
theory") has been proposed by Ketan Mulmuley, and is being actively
pursued by him and a number of other researchers.

While the diversity of new tools and ideas used in modern complexity
theory is very welcome, it also brings new challenges. The main
challenge is to ensure that the field stays united, and that different
sub-areas of computational complexity interact with each other. Such
exchange of ideas is of utmost importance for the continued progress
in complexity theory. Another challenge is to ensure that the
complexity community remains focussed on the fundamental problems in
the field, such as the "P vs NP" and related big open questions.

The proposed workshop aims at addressing both of these challenges. We
plan to bring together some of the most active researchers in various
sub-areas of computational complexity to review the state of the art,
examine the power and limitations of new techniques, and suggest new
directions for research, with the emphasis on the fundamental open
questions in complexity theory. We also plan to invite a number of
senior grad students and postdocs to ensure that the young researchers
are aware of the ideas and tools from different sub-areas of
complexity theory, and to encourage their interest and willingness to
work on hard open problems. We believe that such a workshop will help
keep the complexity theory a vibrant field of research, with fruitful
interactions among different branches of complexity and mathematics,
and the sharp focus on the foundational questions.