Programs | Fall 2013Real Analysis in Computer Science
22 August to 20 December, 2013
Analytical tools 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.
Elchanan Mossel (UC Berkeley; chair), Gil Kalai (Hebrew University, Jerusalem), Subhash Khot (NYU), Michel Ledoux (University of Toulouse), Prasad Raghavendra (UC Berkeley), Luca Trevisan (Stanford).
Long-Term Participants (in addition to Organizers):
Sergey Bobkov (University of Minnesota), Andrej Bogdanov (Chinese University of Hong Kong), Pietro Caputo (University of Rome III), Praladh Harsha (TATA Institute), Johan Håstad (KTH Stockholm), Hamed Hatami (McGill University), Varun Kanade (UC Berkeley), Bruce Kapron (University of Victoria), Guy Kindler (Hebrew University, Jerusalem), Gillat Kol (Weizmann Institute), Nati Linial (Hebrew University, Jerusalem), Krzysztof Oleszkiewicz (University of Warsaw), Ran Raz (Weizmann Institute), Muli Safra (Tel Aviv University), Alex Samorodnitsky (Hebrew University, Jerusalem), Prasad Tetali (Georgia Tech), Julia Wolf (École Polytechnique).
Anindya De (UC Berkeley), Yuval Filmus (University of Toronto), Steven Heilman (NYU), Alexandra Kolla (UIUC), Sushant Sachdeva (Princeton), Dominik Scheder (Aarhus University; joint with Tsinghua), Andrew Wan (Tsinghua/Harvard), Karl Wimmer (Duquesne University), Mary Wootters (University of Michigan), Yi Wu (Purdue)
During the semester there will be three workshops spanning the topics of the program, as well as a Boot Camp designed to acquaint participants with key material early in the semester. These are planned as follows:
- Workshop 1 : "Real Analysis in Testing, Learning and Inapproximability." August 26-30, 2013.
Organizers: Johan Håstad (KTH Stockholm), Subhash Khot (NYU), Prasad Raghavendra (UC Berkeley), Rocco Servedio (Columbia).
- Boot Camp : September 9-13, 2013.
Organizers: Elchanan Mossel (UC Berkeley).
- Workshop 2: "Functional Inequalities in Discrete Spaces with Applications." Sept 30-Oct 4, 2013.
Organizers: Gil Kalai (Hebrew University), Michel Ledoux (Toulouse), Oded Regev (Courant Institute, NYU), Alex Samorodnitsky (Hebrew University).
- Workshop 3 : "Neo-Classical Methods in Discrete Analysis." December 2-6, 2013.
Organizers: Luca Trevisan (Stanford), Julia Wolf (École Polytechnique).
Those interested in participating in this program should send email to the organizers at this address.