Fall 2021

Rigorous Evidence for Information-Computation Trade-offs

Sep. 13Sep. 17, 2021

Add to Calendar


Sam Hopkins (UC Berkeley; co-chair), Lenka Zdeborová (EPFL, Switzerland; 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 rigorous 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 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, 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. 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: 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? 

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).