Real Analysis in Computer Science

Aug. 22–Dec. 20, 2013

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:

Elchanan Mossel (UC Berkeley; chair), Gil Kalai (Hebrew University of Jerusalem), Subhash Khot (Courant Institute, NYU), Michel Ledoux (University of Toulouse), Prasad Raghavendra (UC Berkeley), Luca Trevisan (Stanford University)

Long-Term Participants (including Organizers):

Ron Blei (University of Connecticut), Sergey Bobkov (University of Minnesota), Andrej Bogdanov (Chinese University of Hong Kong), Pietro Caputo (Università Roma Tre), Ilias Diakonikolas (University of Southern California), Prahladh Harsha (Tata Institute of Fundamental Research), Johan Håstad (KTH Royal Institute of Technology), Hamed Hatami (McGill University), Gil Kalai (Hebrew University of Jerusalem), Varun Kanade (UC Berkeley), Bruce Kapron (University of Victoria), Guy Kindler (Hebrew University of Jerusalem), Gillat Kol (Institute for Advanced Study, Princeton), Michel Ledoux (University of Toulouse), Nati Linial (Hebrew University of Jerusalem), Elchanan Mossel (UC Berkeley; chair), Joe Neeman (University of Texas, Austin), Krzysztof Oleszkiewicz (University of Warsaw), Prasad Raghavendra (UC Berkeley), Ran Raz (Weizmann Institute), Muli Safra (Tel Aviv University), Alex Samorodnitsky (Hebrew University of Jerusalem), Prasad Tetali (Georgia Institute of Technology), Luca Trevisan (Stanford University), Julia Wolf (University of Bristol)

Research Fellows:

Anindya De (UC Berkeley), Yuval Filmus (Institute for Advanced Study, Princeton), Steven Heilman (UCLA), Alexandra Kolla (University of Illinois at Urbana-Champaign), Sushant Sachdeva (Yale University), Dominik Scheder (Shanghai Jiao Tong University), Andrew Wan (Tsinghua University; Google Research Fellow), Karl Wimmer (Duquesne University), Mary Wootters (Carnegie Mellon University), Yi Wu (Purdue University)

Visiting Graduate Students and Postdocs:

Naman Agarwal (University of Illinois, Urbana-Champaign), Anand Louis (Princeton University), Piotr Nayar (University of Warsaw), Tomasz Tkocz (University of Warwick), Cenny Wenner (KTH Royal Institute of Technology and Stockholm University), Yixin Xu (Rutgers University)

Workshops

Real Analysis in Testing, Learning and Inapproximability

Monday, Aug. 26–Friday, Aug. 30, 2013

Organizers:

Prasad Raghavendra (UC Berkeley; chair), Johan Håstad (KTH Royal Institute of Technology), Subhash Khot (Courant Institute, NYU), Rocco Servedio (Columbia University)

Real Analysis Boot Camp

Monday, Sep. 9–Friday, Sep. 13, 2013

Organizers:

Elchanan Mossel (UC Berkeley)

Functional Inequalities in Discrete Spaces with Applications

Monday, Sep. 30–Friday, Oct. 4, 2013

Organizers:

Alex Samorodnitsky (Hebrew University of Jerusalem; chair), Gil Kalai (Hebrew University of Jerusalem), Michel Ledoux (University of Toulouse), Oded Regev (Courant Institute, NYU)

Neo-Classical Methods in Discrete Analysis

Monday, Dec. 2–Friday, Dec. 6, 2013