Fall 2021

Rigorous Evidence for Information-Computation Trade-offs

Sep 13, 2021 to Sep 17, 2021 

Add to Calendar


Sam Hopkins (UC Berkeley; Microsoft Research Fellow; co-chair), Lenka Zdeborová (École polytechnique fédérale de Lausanne; co-chair), Afonso Bandeira (ETH Zürich)

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.

If you are interested in joining this workshop, please see the Participate page.

Registration is required to attend this workshop. Space may be limited, and you are advised to register early. To submit your name for consideration, please register and await confirmation of your acceptance before booking your travel.

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)