Topic Description

In classical statistics, the focus has primarily been on how inferential accuracy improves with an increasing number of data points—with no attention given to computational complexity. Indeed, when constrained to achieve a specific level of accuracy within a limited timeframe, classical statistical theory does not provide guidance on how to devise an effective inferential strategy. Ideally, one would like to develop a statistically optimal method for a given task that is also computationally efficient. In various contexts, however, it appears that statistical optimality and computational tractability are at odds with each other. A key question is whether these tradeoffs are inherent. An information-computation (IC) tradeoff for a statistical task describes a scenario where no computationally efficient algorithm can achieve the information-theoretic limits.

When faced with a statistical task, how can we determine if an IC tradeoff exists? Unfortunately, traditional methods from worst-case complexity theory, such as NP-hardness, seem inadequate for this purpose. Recent work at the interface of theoretical computer science and statistics has made notable progress in our understanding of this broad question. Roughly speaking, two interconnected approaches have emerged. One approach, similar to classical complexity theory, involves developing efficient reductions from problems believed to be hard on average (e.g., planted clique or LWE). The other approach focuses on establishing unconditional lower bounds within broad (yet restricted) computational models—such as Statistical Query (SQ) algorithms, low-degree polynomials, and Sum-of-Squares (SoS) algorithms. These complementary methodologies have provided strong evidence of IC tradeoffs across various statistical tasks. Despite these recent advances, we are still a long way from a unified theory that identifies the underlying causes of these tradeoffs.

Objectives

The workshop will provide an introduction to IC tradeoffs in statistical tasks, covering recent techniques, results, and emerging research directions. While the workshop is designed to be accessible to a broad theoretical computer science and statistics audience, it will also emphasize significant recent advances and open questions. Some key questions to be addressed during the workshop include: What IC tradeoffs are currently known for central average-case problems (e.g., planted clique, NGCA, sparse PCA)? How can we further expand the scope of IC tradeoffs to problems where our understanding remains poor? What are the connections between various restricted computational models (e.g., SQ and SoS algorithms), and how do lower bounds in these models relate to reduction-based hardness? Under what circumstances can we overcome lower bounds in restricted models? Ultimately, we aim for this workshop to lay the groundwork for more researchers to engage with the field, potentially leading to further progress and connections with other areas of study.

List of Participants (Tentative)

Ilias Diakonikolas (UW Madison)
Chao Gao (U Chicago)
Jingyi Gao (UW Madison)
Yiding Hua (ETH)
Brice Huang (MIT)
He Jia (Northwestern)
Giannis Iakovidis (UW Madison)
Chris Jones (Bocconi)
Daniel Kane (UCSD)
Fred Koehler (U Chicago)
Tim Kunisky (Johns Hopkins)
Jerry Li (UW)
Sihan Liu (UCSD)
Yuetian Luo (U Chicago)
Mingchen Ma (UW Madison)
Ansh Nagda (Berkeley)
Shuo Pang (Bristol)
Ankit Pensia (Simons Institute)
Thanasis Pittas (UW Madison)
Aaron Potechin (U Chicago)
Lisheng Ren (UW Madison)
Cynthia Rush (Columbia)
Mark Sellke (Harvard)
David Steurer (ETH)
Neekon Vafa (MIT)
Aravindan Vijayaraghavan (Northwestern)
Alex Wein (UC Davis)
Jeff Xu (CMU)
Xifan Yu (Yale)
Ilias Zadik (Yale)
Nikos Zarifis (UW Madison)

Schedule

Monday (June 16)

Time	Talk
8:45-9:15	Continental Breakfast
9:15-9:30	Address by Avrim Blum
9:30-10:30	Alex Wein (UC Davis) Low-Degree Polynomials: Overview and Recent Developments
10:30-11:00	Coffee Break
11:00-11:45	Jerry Li (UW) Rigorous Implications of the Low-Degree Heuristic
11:45-12:45	Lunch at TTIC
12:45-01:45	Mark Sellke (Harvard) Recent Developments on the Overlap Gap Property
1:45-2:30	Brice Huang (MIT) Algorithmic threshold for the random perceptron
2:30-2:45	Coffee Break
2:45-3:30	Tim Kunisky (Johns Hopkins) Lower bounds against low coordinate degree algorithms
3:30-4:15	Sihan Liu (UCSD) PTF Lower Bounds for Non-Gaussian Component Analysis
4:15-4:30	Coffee Break
4:30 - 5:30	Open Problems Session

Tuesday (June 17)

Time	Talk
9:00-9:30	Continental Breakfast
9:30-10:30	David Steurer (ETH) From proofs to algorithms: robust and private statistics via sum-of-squares
10:30-11:00	Coffee Break
11:00-12:00	Aaron Potechin (U Chicago) Sum of Squares Lower Bounds for Average Case Problems
12:00-1:00	Lunch at TTIC
1:00-1:45	Shuo Pang (Bristol) Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis: Challenges and New Techniques
1:45 - 2:30	Jeff Xu (CMU) SoS Lower Bounds for Coloring Random Graphs
2:30-2:45	Coffee Break
2:45-3:15	Ankit Pensia (UC Berkeley) SoS Certifiability of Subgaussian Distributions
3:15-4:00	Chris Jones (Bocconi) What is a Feynman diagram?
4:00-4:15	Coffee Break
4:15-5:00	Ilias Zadik (Yale) The (optimized) Franz-Parisi criterion and its equivalence with LD/SQ lower bounds

Wednesday (June 18)

Time	Talk
9:00-9:30	Continental Breakfast
9:30-10:30	Cynthia Rush (Columbia) Survey on AMP
11:30-11:00	Coffee Break
11:00-12:00	Fred Koehler (U Chicago) Recent Developments on Sparse Linear Regression
12:00-1:30	Lunch (on your own)
1:30-2:10	Neekon Vafa (MIT) Reducing Lattice Problems to Statistical Tasks via (Continuous) Learning With Errors
2:10-2:50	Lisheng Ren (UW Madison) Hardness of Learning Halfspaces under the LWE assumption
2:50-3:30	Ansh Nagda (UC Berkeley) On optimal distinguishers for planted clique
3:30-3:40	Coffee Break
3:40-4:20	Mingchen Ma (UW Madison) Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
4:20-5:00	Giannis Iakovidis (UW Madison) Information-Computation Tradeoffs in Learning Multi-Index Models