Computational Complexity (10w5028)
Organizers
Valentine Kabanets (Simon Fraser University)
Paul Beame (University of Washington)
Stephen Cook (University of Toronto)
Russell Impagliazzo (University of California, San Diego)
Avi Wigderson (Institute for Advanced Study)
Objectives
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. Recently, a completely elementary, combinatorial, explicit construction of expander graphs has been found by complexity theorists Reingold, Vadhan, and Wigderson. For an even more recent example, the finite-field version of the famous Kakeya conjecture has been solved this year by another complexity theorist, Zeev Dvir, and then used for an explicit construction of randomness extractors, combinatorial objects with many applications in complexity theory.
As the field of complexity theory matures, its tools become more sophisticated. On the one hand, such sophistication of the available tools and techniques is welcome as it provides more avenues for attacking the many open questions in complexity. On the other hand, this makes it more challenging for the field to stay united, as it is difficult for an individual researcher to develop expertise in all relevant areas of mathematics.
At the same time, it is very important for the various emerging sub-areas of complexity to stay connected with each other, and continue the fruitful exchange of ideas. The research in computational complexity has always been characterized by a high degree of interpenetration of ideas from different fields of computer science and mathematics, and the main goal of the proposed workshop is to help ensure that this valuable practice continues. To this end, we plan to bring together some of the most active researchers in various sub-areas of computational complexity as well as a few senior graduate students and postdocs, to discuss various new methods and tools used in complexity, understand their power and limitation, and suggest new potentially useful methods. We believe that the proposed workshop will both lead to some new technical results, and help shape the new research directions in complexity theory.
