About

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 hypercontractive 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, computational learning, computational social choice, and communication complexity. The goal of this program was to bring together mathematicians and computer scientists to study influences, measures of complexity of discrete functions, functional inequalities, invariance principles, nonclassical norms, representation theory, and other modern topics in mathematical analysis and their applications to theoretical computer science.

View the list of open problems written by Y. Filmus, H. Hatami, S. Heilman, E. Mossel, R. O’Donnell, S. Sachdeva, A. Wan, and K. Wimmer in connection with this program.

Organizers

Long-Term Participants (including Organizers)

Gillat Kol (Institute for Advanced Study, Princeton)

Research Fellows

Andrew Wan ( Institute for Defense Analyses; Google Research Fellow)

Visiting Graduate Students and Postdocs

Cenny Wenner (KTH Royal Institute of Technology and Stockholm University)