Program
s
Fall 2020

Probability, Geometry, and Computation in High Dimensions

Aug. 19Dec. 18, 2020

In recent years, the proliferation of learning and statistical inference tasks on complex data has led to renewed focus on the development of theory for the high-dimensional setting. In the existing literature on such problems, it is notable that many fruitful ideas have emerged from the interplay among probability, geometry, and computation in the high-dimensional setting. For instance, the phenomenon of "concentration of measure" lies at the intersection of probability and geometry and is related to the problem of dimension-free guarantees for many important algorithms. Another example is the contribution of ideas from statistical physics toward both algorithm design and probabilistic analysis, which has led to advances in understanding for some classical problems in computer science.

High-dimensional problems have attracted the attention of researchers from across diverse fields of research: computer scientists, mathematicians, physicists, and statisticians have all contributed analytical tools, conceptual advances, and new problem directions. Despite much recent progress, important basic questions remain open, for instance: Which properties of data can be learned from a small number of samples? Can we characterize general trade-offs between the quality of data (statistical information) and the availability of computational resources? For what kinds of problems is it possible to make algorithmic guarantees that are dimension free or have minimal dimension dependence? Beyond the immediate applications, these questions are also related to fundamental questions in approximation theory, convex geometry, and classical models of physical systems.

In advancing our understanding of these problems, it becomes increasingly clear that several traditionally separate fields will have a role to play. Although this sense is widely shared, communication of ideas across different research domains has remained relatively limited, and cultural differences have led different groups to study similar problems but with different framings or in different regimes. This semester program aims to advance the state of research on high-dimensional settings by bringing together a diverse range of research perspectives.

Organizers:

Nike Sun (Massachusetts Institute of Technology; chair), Jian Ding (University of Pennsylvania), Ronen Eldan (Weizmann Institute), Elchanan Mossel (Massachusetts Institute of Technology), Joe Neeman (University of Texas at Austin), Jelani Nelson (UC Berkeley), Tselil Schramm (Stanford University; Microsoft Research Fellow)

Long-Term Participants (including Organizers):

Anirban Basak (Tata Institute of Fundamental Research), Guy Bresler (Massachusetts Institute of Technology), Sébastien Bubeck (Microsoft Research), Clément Canonne (IBM Research Almaden), Thomas Courtade (UC Berkeley), Daniel Dadush (Centrum Wiskunde & Informatica), Anindya De (University of Pennsylvania), Amir Dembo (Stanford University), Jian Ding (University of Pennsylvania), Ronen Eldan (Weizmann Institute), Steven Evans (UC Berkeley), David Gamarnik (Massachusetts Institute of Technology), Shirshendu Ganguly (UC Berkeley), Nika Haghtalab (Cornell University), Daniel Kane (UC San Diego), Ravi Kannan (Microsoft Research India), Adam Klivans (University of Texas at Austin), Florent Krzakala (École Normale Supérieure Paris), Yin Tat Lee (University of Washington), Song Mei (UC Berkeley), Dor Minzer (Massachusetts Institute of Technology), Andrea Montanari (Stanford University), Cris Moore (Santa Fe Institute), Elchanan Mossel (Massachusetts Institute of Technology), Joe Neeman (University of Texas at Austin), Jelani Nelson (UC Berkeley), Miklos Racz (Princeton University), Kavita Ramanan (Brown University), Ronitt Rubinfeld (Massachusetts Institute of Technology), Mark Rudelson (University of Michigan), Barna Saha (UC Berkeley), Alistair Sinclair (UC Berkeley), Allan Sly (Princeton), Nikhil Srivastava (UC Berkeley), Jacob Steinhardt (UC Berkeley), Nike Sun (Massachusetts Institute of Technology; chair), Avishay Tal (UC Berkeley), Prasad Tetali (Georgia Institute of Technology), Martin Wainwright (UC Berkeley), Alex Wein (New York University), Elisabeth Werner (Case Western Reserve University), Mary Wootters (Stanford University), Jiaming Xu (Duke University), Lenka Zdeborová (CNRS), Tianyi Zheng (UC San Diego)

Research Fellows:

Ahmed El Alaoui (Simons Institute, UC Berkeley; RMKarp Research Fellow), Aditya Grover (Facebook AI Research; Google Research Fellow), Vishesh Jain (Simons Institute, UC Berkeley), Galyna Livshyts (Georgia Institute of Technology), Ashwin Pananjady (Simons Institute, UC Berkeley; Swiss Re Research Fellow), Cindy Rush (Columbia University; NTT Research Fellow), Tselil Schramm (Stanford University; Microsoft Research Fellow), Erik Waingarten (Stanford University)

Visiting Graduate Students and Postdocs:

Taejoo Ahn (UC Berkeley), Maryam Aliakbarpour (Massachusetts Institute of Technology), Ainesh Bakshi (Carnegie Mellon University), Jess Banks (UC Berkeley), Enric Boix (Massachusetts Institute of Technology), Matthew Brennan (Massachusetts Institute of Technology), Michael Celentano (Stanford University), Kabir Chandrasekher (Stanford University), Michael Chang (UC Berkeley), Yeshwanth Cherapanamjeri (UC Berkeley), Rishabh Dudeja (Columbia University), Majid Farhadi (Georgia Institute of Technology), Margalit Glasgow (Stanford University), Sam Hopkins (UC Berkeley), Brice Huang (Massachusetts Institute of Technology), Sophie Huiberts (Centrum Wiskunde & Informatica), Rajesh Jayaram (Carnegie Mellon University), Haotian Jiang (University of Washington), Tarun Kathuria (UC Berkeley), Seri Khoury (UC Berkeley), Michael Kim (UC Berkeley), Eren Can Kizildag (Massachusetts Institute of Technology), Tomasz Kociumaka (Bar-Ilan Univeristy), Frederic Koehler (Massachusetts Institute of Technology), Ben Li (Tel Aviv University), Noam Lifshitz (Hebrew University), Siqi Liu (UC Berkeley), Theo McKenzie (UC Berkeley), Dan Mikulincer (Weizmann Institute), Sidhanth Mohanty (UC Berkeley), Dheeraj Nagaraj (Massachusetts Institute of Technology), Chinmay Nirkhe (UC Berkeley), Mark Sellke (Stanford University), Ewin Tang (University of Washington), Anna Thomas (Stanford University), Kevin Tian (Stanford University), Jorge Garza Vargas (UC Berkeley), Prayaag Venkat (Harvard University), Xinyu Wu (Carnegie Mellon University), Jeff Xu (Carnegie Mellon University), Dana Yang (Duke University), Elizabeth Yang (UC Berkeley), Fred Zhang (UC Berkeley)

Workshops

Aug. 19Aug. 28, 2020

Organizers:

Nike Sun (Massachusetts Institute of Technology; chair), Jian Ding (University of Pennsylvania), Ronen Eldan (Weizmann Institute), Elchanan Mossel (Massachusetts Institute of Technology), Joe Neeman (University of Texas at Austin), Jelani Nelson (UC Berkeley), Tselil Schramm (Stanford University; Microsoft Research Fellow)
Sep. 21Sep. 25, 2020

Organizers:

Cris Moore (Santa Fe Institute; co-chair), Ryan O'Donnell (Carnegie Mellon University; co-chair), David Gamarnik (Massachusetts Institute of Technology), Andrea Montanari (Stanford University), Lenka Zdeborová (CNRS)
Oct. 19Oct. 23, 2020

Organizers:

Bo'az Klartag (Weizmann Institute of Science; chair), Ramon Van Handel (Princeton University), James R. Lee (University of Washington), Jelani Nelson (UC Berkeley), Prasad Tetali (Georgia Institute of Technology)
Dec. 14Dec. 18, 2020

Organizers:

Adam Klivans (University of Texas at Austin; chair), Guy Bresler (Massachusetts Institute of Technology), Sébastien Bubeck (Microsoft Research), Anindya De (University of Pennsylvania), Philippe Rigollet (Massachusetts Institute of Technology)

 Subscribe to the program calendar.

Past Internal Program Activities

Tuesday, December 8th 11:00 am12:00 pm
Amin Coja-Oghlan, Goethe University
Monday, December 7th 10:00 am11:30 am
Tuesday, December 1st 11:00 am12:00 pm
Adam Klivans (University of Texas, Austin)
Thursday, November 19th 1:00 pm2:00 pm
Christina Yu (Cornell University)
Thursday, November 12th 1:00 pm2:00 pm
Vidya Muthukumar (UC Berkeley)
Tuesday, November 10th 11:00 am12:00 pm
Cris Moore (Santa Fe Institute)
Tuesday, November 3rd 11:00 am12:00 pm
Yin Tat Lee (University of Washington)
Thursday, October 29th 1:00 pm2:00 pm
Vishesh Jain (UC Berkeley)
Tuesday, October 27th 11:00 am12:00 pm
Elisabeth Werner (Case Western Reserve University)
Thursday, October 22nd 1:00 pm2:00 pm
Jalaj Bhandari (Columbia University)
Thursday, October 15th 1:00 pm2:00 pm
Tselil Schramm (Stanford University); Zhuoran Yang (Princeton University)
Tuesday, October 13th 11:00 am12:00 pm
Shiri Artstein (Tel-Aviv University)
Tuesday, October 6th 11:00 am12:00 pm
Sam Hopkins, UC Berkeley
Tuesday, September 29th 11:00 am12:00 pm
Dana Ron, Tel-Aviv University
Thursday, September 24th 1:00 pm2:00 pm
Ashwin Pananjady, UC Berkeley
Thursday, September 17th 1:00 pm2:00 pm
Cindy Rush (Columbia University) & Erik Waingarten (Stanford University)
Tuesday, September 15th 11:00 am12:00 pm
Mark Rudelson (University of Michigan)
Thursday, September 10th 1:00 pm2:00 pm
Galyna Livshyts (Georgia Institute of Technology) & Lin Yang (UCLA)
Tuesday, September 8th 11:00 am12:00 pm
Anindya De (University of Pennsylvania)
Thursday, September 3rd 10:00 am11:00 am
Andrea Montanari (Stanford University)
Thursday, August 27th 1:00 pm1:45 pm
Ahmed El Alaoui, Stanford University