In modern statistical problems, there is an inherent trade-off between statistical and computational resources. The goal of this workshop is to better understand this trade-off. 

The community of researchers addressing these questions is diverse, spanning statistics, computer science, information theory, and physics, reflecting the universal nature of this phenomenon. The rigorous approaches used to explain and predict information-computation trade-offs are similarly diverse. At a high level, they can be classified broadly as (1) demonstrating hardness for restricted computational models and (2) conditional hardness based on reductions from conjecturally hard problems such as planted clique. Popular restricted computational models include sum-of-squares relaxations and other convex programming hierarchies, statistical query algorithms, multiple notions of local algorithms, local- and gradient-based algorithms, and various classes of circuits, among others.

Our understanding of the relationships among these varied approaches is limited. For each statistics problem that emerges, researchers apply a variety of these methods to predict information-computation trade-offs. Each method results in a distinct piece of evidence, and the disparate pieces must then be reconciled. A more coherent understanding is needed, and this workshop aims to bring together researchers working on this topic to address questions such as these: Is there a hierarchy in mathematical strength of these computational hardness predictions? Are some of these predictions better suited to certain types of problems? When do we expect that these predictions are actually accurate? How can we develop even more convincing evidence for fundamental computational limits in statistics? 

EPFL will host a mirror workshop, organized by Lenka Zdeborova and Afonso Bandeira, on September 14-16, on related topics. Three sessions will be joint with the EPFL workshop via Zoom, including talks and opportunities for questions from attendees at both workshops.

This event will be held in person and virtually.

Invited Participants

Jayadev Acharya (Cornell University), Ahmed Alaoui (), Jess Banks (UC Berkeley), Guy Bresler (Massachusetts Institute of Technology), Yuxin Chen (Princeton University), Maria Chiara Angelini (Sapienza - Università di Roma), Ilias Diakonikolas (University of Wisconsin-Madison), Sumegha Garg (Harvard University), Reza Gheissari (UC Berkeley), Surbhi Goel (Microsoft Research NYC), Paul Hand (Northeastern University), Samuel Hopkins (UC Berkeley), Brice Huang (Massachusetts Institute of Technology), Aukosh Jagannath (University of Waterloo), Chris Jones (University of Chicago), Daniel Kane (UC San Diego), Sushrut Karmalkar (University of Wisconsin-Madison), Pravesh Kothari (Carnegie Mellon University), Pravesh K. Kothari (), Florent Krzakala (École polytechnique fédérale de Lausanne), Tim Kunisky (NYU), Jerry Li (Microsoft Research), Andrea Lincoln (UC Berkeley), Bruno Loureiro (EPFL), Antoine Maillard (Ecole Normale Supérieure (Paris)), Song Mei (UC Berkeley), Ryan O'Donnell (Carnegie Mellon University), Ashwin Pananjady (Georgia Institute of Technology), Ankit Pensia (University of Wisconsin - Madison), Aaron Potechin (University of Chicago), Cynthia Rush (Columbia University), Tselil Schramm (Stanford University), Mark Sellke (Stanford), Nathan Srebro (Toyota Technological Institute at Chicago), Jonathan Ullman (Northeastern University), Gregory Valiant (Stanford University), Umesh Vazirani (UC Berkeley), Alexander Wein (UC Berkeley), Yuling Yan (Princeton University), Ilias Zadik (Massachusetts Institute of Technology), Lenka Zdeborová (École polytechnique fédérale de Lausanne), Susanna F. de Rezende (Czech Academy of Sciences)