Fall 2021

Rigorous Evidence for Information-Computation Trade-offs

Sep. 13Sep. 17, 2021

Add to Calendar


Sam Hopkins (UC Berkeley & Massachusetts Institute of Technology; co-chair), Lenka Zdeborová (CEA Saclay and CNRS; co-chair)

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

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 approaches used to explain and predict information-computation tradeoffs 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. 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, various classes of circuits, among others.

Our understanding of the relationships between these varied approaches is limited. For each statistics problem that emerges, researchers apply a variety of these methods to predict information-computation tradeoffs, and each results in a disparate piece of evidence that must then be reconciled with the others. A more coherent understanding is needed, and this workshop aims to bring together researchers working on this topic to address questions such as: Is there a hierarchy in strength of these 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 computational limits? 

All events take place in the Calvin Lab auditorium.

Further details about this workshop will be posted in due course. Enquiries may be sent to the organizers workshop-si1 [at] (at this address).