Rigorous Evidence for Information-Computation Trade-offs

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.