Real Analysis in Testing, Learning and Inapproximability
Organizers:
The goal of the first workshop of the program is to identify challenges from learning, computational complexity, hardness of approximation and communication complexity that can be explicitly expressed in discrete analytic terms. This will provide a basis for the program in terms of some of the central problems to be studied. In particular, Fourier analysis plays a key role in property testing, in hardness of approximation and in additive combinatorics by providing tools to differentiate between families of functions that “pass” certain tests and functions that “do not pass” the same tests. Examples of such tests include checking for linearity, for having a high influence variable, and for having an additive structure. The workshop will investigate different techniques for analyzing tests and their applications, as well as related problems in learning and computational complexity.
Enquiries may be sent to the organizers workshop_realanalysis1 [at] lists.simons.berkeley.edu (at this address.)
Anil Ada (McGill University), Naman Agarwal (University of Illinois, Urbana-Champaign), Eli Ben-Sasson (Technion Israel Institute of Technology), Eric Blais (Massachusetts Institute of Technology), Andrej Bogdanov (Chinese University of Hong Kong), Pietro Caputo (Roma Tre University), Siu On Chan (UC Berkeley), Anindya De (UC Berkeley), Ilias Diakonikolas (University of Edinburgh), Yuval Filmus (University of Toronto), Parikshit Gopalan (Microsoft Research), Venkatesan Guruswami (Carnegie Mellon University), Elad Haramaty (Technion Israel Institute of Technology), Prahladh Harsha (Tata Institute of Fundamental Research), Johan Håstad (KTH Royal Institute of Technology), Hamed Hatami (McGill University), Steven Heilman (Courant Institute, NYU), Sangxia Huang (KTH Royal Institute of Technology), Ming Jin (UC Berkeley), Gil Kalai (Hebrew University of Jerusalem), Varun Kanade (UC Berkeley), Daniel Kane (Stanford University), Bruce Kapron (University of Victoria), Subhash Khot (Courant Institute, NYU), Anthony Kim (Stanford University), Guy Kindler (Hebrew University of Jerusalem), Adam Klivans (University of Texas, Austin), Gillat Kol (Technion Israel Institute of Technology), Michel Ledoux (University of Toulouse), James R. Lee (University of Washington), Lisha Li (UC Berkeley), Nati Linial (Hebrew University of Jerusalem), Raghu Meka (Microsoft Research), Dana Moshkovitz (Massachusetts Institute of Technology), Elchanan Mossel (UC Berkeley), Joe Neeman (UC Berkeley), Ryan O'Donnell (Carnegie Mellon University), Krzysztof Oleszkiewicz (University of Warsaw), Prasad Raghavendra (UC Berkeley), Ran Raz (Weizmann Institute), Sushant Sachdeva (Princeton University), Muli Safra (Tel Aviv University), Rishi Saket (IBM T.J. Watson Research Center), Alex Samorodnitzky (Hebrew University of Jerusalem), Dominik Scheder (Aarhus University), Rocco Servedio (Columbia University), Alexander Sherstov (UCLA), David Steurer (Cornell University), Li-Yang Tan (Columbia University), Prasad Tetali (Georgia Institute of Technology), Luca Trevisan (Stanford University), Madhur Tulsiani (Toyota Technological Institute, Chicago), Ben Lee Volk (Technion Israel Institute of Technology), Andrew Wan (Harvard University), Cenny Wenner (KTH Royal Institute of Technology and Stockholm University), Karl Wimmer (Duquesne University), Julia Wolf (University of Bristol), Mary Wootters (University of Michigan), Pratik Worah (University of Chicago), John Wright (Carnegie Mellon University), Yi Wu (Purdue University), Ying Xiao (Georgia Institute of Technology), Yuan Zhou (Carnegie Mellon University).
