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.
