Tools from analysis are useful in the study of many problems in theoretical computer science. Perhaps surprisingly, in many cases discrete features of problems allow the application of sophisticated analytical tools. A seminal example of this phenomenon is the use of hyper-contractive inequalities in the analysis of Boolean functions, as first demonstrated by Kahn, Kalai and Linial.
Results in discrete analysis play an important role in hardness of approximation, in computational learning, in computational social choice and in communication complexity. The goal of this program is to bring together mathematicians and computer scientists to study influences, measures of complexity of discrete functions, functional inequalities, invariance principles, non-classical norms, representation theory and other modern topics in mathematical analysis and their applications to theoretical computer science.
Long-Term Participants (including Organizers):
Visiting Graduate Students and Postdocs:
Program image by Guy Kindler.