[Computational Complexity] Analysis in Complexity
- A shout out to my colleagues who have gathered in Banff for the BIRS workshop on Analytic Tools in Computational Complexity.
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.I started graduate work in complexity right before the algebraic revolution that drove Razborov-Smolensky's circuit lower bounds, Toda's Theorem on the power of the permanent, the power of interactive and probabilistically checkable proofs and much more. But now, two decades later, algebraic techniques are producing diminishing returns and we have seen a growth in using real analysis in complexity as highlighted by this workshop. Avi Wigderson is giving a two-hour survey on "The Power of Partial Derivatives." Hard to have imagined a connection between partial derivatives and complexity.
What about those of us who went into computational complexity because we enjoyed discrete math? Should an old dog like me try to learn new tricks? Ah, the challenge of keeping up with a field that moves in mysterious new ways.
Posted By Lance to Computational Complexity at 8/04/2008 06:54:00 AM