Fall 2021

Rigorous Evidence for Information-Computation Trade-offs

Sep 13, 2021 to Sep 17, 2021 

Add to Calendar


Sam Hopkins (UC Berkeley; 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.

Inquiries may be sent to the organizers workshop-si1 [at] (at this address).

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.