‹ Programs & Events
‹ Programs
‹ Past Programs
Real Analysis in Computer Science
Aug. 22 – Dec. 20, 2013
Download Program Report
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.
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)
Real Analysis in Testing, Learning and Inapproximability
Aug. 26 – Aug. 30, 2013
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
Sep. 9 – Sep. 13, 2013
Elchanan Mossel (UC Berkeley)
Functional Inequalities in Discrete Spaces with Applications
Sep. 30 – Oct. 4, 2013
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
Dec. 2 – Dec. 6, 2013
Luca Trevisan (Stanford University), Julia Wolf (University of Bristol)
Real Analysis Reunion Workshop
Dec. 9 – Dec. 11, 2014
Elchanan Mossel (UC Berkeley), Luca Trevisan (Stanford University)
Program image by Guy Kindler.
Past Internal Program Activities
Real Analysis Weekly Seminar
Thursday, December 12 11:00 am – 12:00 pm
Real Analysis Open Problem Session
Monday, November 25 1:00 pm – 3:00 pm
Thursday, November 21 11:00 am – 12:00 pm
Thursday, November 7 11:00 am – 12:00 pm
Thursday, October 31 11:00 am – 1:00 pm
Real Analysis Day
Wednesday, October 30 10:00 am – 5:00 pm
Thursday, October 24 11:00 am – 12:00 pm
Real Analysis Seminars
Thursday, September 26 11:00 am – 1:00 pm
Thursday, September 5 11:00 am – 1:00 pm
Start date: Real Analysis in Computer Science
Current & Future Programs