Computational Complexity of Statistical Problems Workshop

MIT. Cambridge, MA. June 14-16, 2023 (tutorial days June 12-13)


Register hereregistration is free but mandatory


The objective of the workshop is to help advance the methodology for reasoning about the computational complexity of statistical estimation. Over the last decade several communities and lines of work have begun to make progress on the core questions of the field. This workshop aims to highlight recent progress and form new collaborations among researchers from complexity theory, algorithms, statistics, learning theory, probability, information theory, and statistical physics.


The workshop will take place at MIT on June 14-16, 2023 and will be held in Building 1, Room 1-190. We will also have two tutorial days June 12-13 in the same location: 1-190.

POSTER SUBMISSIONS: There will be a poster session on the first day of the workshop, June 14. Poster submissions are welcome from all. To present a poster, please submit a brief (1-3 paragraphs) abstract to by May 19, and a response will be given by May 23.


  • Guy Bresler (MIT)
  • Sam Hopkins (MIT)
  • Prasad Raghavendra (UC Berkeley)
  • Nike Sun (MIT)

Tutorial Lectures

Day 1: Monday, June 12, 2023

Time (EDT) Speaker Title
9:30 - 10:00 Coffee and snacks
10:00 - 11:00 Vinod Vaikuntanathan (MIT) TBD
11:10 - 12:10 Vinod Vaikuntanathan (MIT) TBD
12:15 - 2:00 Lunch break
2:00 - 3:00 Virginia Vassilevska Williams (MIT) TBD
3:00 - 3:10 Short break
3:10 - 4:10 Virginia Vassilevska Williams (MIT) TBD

Day 2: Tuesday, June 13, 2023

Time (EDT) Speaker Title
9:30 - 10:00 Coffee and snacks
10:00 - 11:00 Kuikui Liu (MIT) TBD
11:10 - 12:10 Kuikui Liu (MIT) TBD
12:15 - 2:00 Lunch break
2:00 - 3:00 Will Perkins (Georgia Tech) The cluster expansion and its statistical and algorithmic applications[Abstract]
I will introduce the cluster expansion, a classical tool from statistical physics used to prove absence of phase transition and describe the phase diagram of spin models on lattices. I'll then show how the cluster expansion can be applied in algorithmic and statistical settings to design efficient sampling algorithms and compute statistical indistinguishability thresholds.
3:00 - 3:10 Short break
3:10 - 4:10 Will Perkins (Georgia Tech) The cluster expansion and its statistical and algorithmic applications

Workshop Program

Day 1: Wednesday, June 14, 2023

Time (EDT) Speaker Title
9:30 - 10:00 Coffee and snacks
10:00 - 10:45 David Steurer (ETH) Algorithms approaching the threshold for semi-random planted clique[Abstract]
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian~\cite{FK01}. The previous best algorithms for this model succeed if the planted clique has size at least \(n^{2/3}\) in a graph with \(n\) vertices (Mehta, Mckenzie, Trevisan, 2019 and Charikar, Steinhardt, Valiant 2017). Our algorithms work for planted-clique sizes approaching \(n^{1/2}\) -- the information-theoretic threshold in the semi-random model~\cite{steinhardt2017does} and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt. Our algorithms are based on higher constant degree sum-of-squares relaxation and rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in \emph{unbalanced} bipartite Erdős--Rényi random graphs into algorithms for semi-random planted clique. The use of a higher-constant degree sum-of-squares is essential in our setting: we prove a lower bound on the basic SDP for certifying bicliques that shows that the basic SDP cannot succeed for planted cliques of size \(k=o(n^2/3)\). We also provide some evidence that the information-computation trade-off of our current algorithms may be inherent by proving an average-case lower bound for unbalanced bicliques in the low-degree-polynomials model. The talk is based on a joint work with Rares-Darius Buhai and Pravesh K. Kothari.
10:45 - 11:30 Tselil Schramm (Stanford) Semidefinite programs simulate approximate message passing robustly [Abstract]
Approximate message passing (AMP) is a family of iterative algorithms that are known to optimally solve many high-dimensional statistics optimization problems. In this talk, I will explain how to simulate a broad class of AMP algorithms in polynomial time using "local statistics hierarchy" semidefinite programs (SDPs), with the added benefit of robustness: the SDPs work even in the strong contamination model, when an unknown (but bounded) subset of the input data is adversarially corrupted. Ours are the first robust guarantees for many of these problems. Further, our results offer an interesting counterpoint to strong lower bounds against less constrained SDP relaxations for problems where AMP is known to succeed. Based on joint work with Misha Ivkov.
11:30 - 12:00 Michael Celentano (UC Berkeley) TBD[Abstract]
12:00 - 2:00 Lunch Break
2:00 - 2:45 Surbhi Goel (UPenn) TBD[Abstract]
2:45 - 3:30 Alex Wein (UC Davis) New Techniques for Low-Degree Lower Bounds [Abstract]
One form of rigorous evidence for computational hardness of statistical problems is low-degree lower bounds, i.e. provable failure of any algorithm that can be expressed as a low-degree multivariate polynomial in the observations. Inspired by sum-of-squares, low-degree lower bounds were first introduced in the context of distinguishing a "planted" distribution from an iid "null" distribution. I will give an overview of some new techniques that allow us to prove low-degree lower bounds in more complicated settings, including "planted-versus-planted" testing, estimation problems, and tensor decomposition.
3:30 - 4:00 Shyam Narayanan (MIT) Robustness Implies Privacy in Statistical Estimation[Abstract]
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a constant fraction of adversarially-corrupted samples. This talk is based on joint work with Sam Hopkins, Gautam Kamath, and Mahbod Majid.
4:00 - 4:30 Break
4:30 - 6:00 Poster Session Poster Session

Day 2: Thursday, June 15, 2023

Time (EDT) Speaker Title
9:30 - 10:00 Coffee and snacks
10:00 - 10:45 Suriya Gunasekar (Microsoft) TBD[Abstract]
10:45 - 11:30 Ronitt Rubinfeld (MIT) TBD[Abstract]
11:30 - 12:00 Sitan Chen (Harvard) Recent Progress on Provably Learning Neural Networks[Abstract]
We present recent upper and lower bounds for the well-studied problem of learning neural networks from Gaussian examples. In the first half, we give the first polynomial-time algorithm for learning arbitrary one-hidden-layer networks of constant width. The algorithm, which can be interpreted as solving a certain tensor decomposition problem in the absence of condition number bounds, is an iterative procedure for recovering “clumps” of neurons at multiple scales. In the second half, we give computational hardness results for learning two-hidden-layer networks. Contrary to conventional wisdom, we are able to prove statistical query lower bounds for a real-valued, noiseless learning problem. The talk is based on joint works with Zehao Dou, Surbhi Goel, Aravind Gollakota, Adam Klivans, and Raghu Meka.
12:00 - 2:00 Lunch Break
2:00 - 2:45 Nati Srebro (TTIC) TBD[Abstract]
2:45 - 3:30 Li-Yang Tan (Stanford) Properly learning decision trees with queries is NP-hard [Abstract]
We prove that it is NP-hard to properly PAC learn decision trees with queries, resolving a longstanding open problem in learning theory (Bshouty 1993; Guijarro-Lavín-Raghavan 1999; Mehta-Raghavan 2002; Feldman 2016). While there has been a long line of work, dating back to (Pitt–Valiant 1988), establishing the hardness of properly learning decision trees from random examples, the more challenging setting of query learners necessitates different techniques and there were no previous lower bounds. En route to our main result, we simplify and strengthen the best known lower bounds for a different problem of decision tree minimization (Zantema–Bodlaender 2000; Sieling 2003). On a technical level, we introduce the notion of hardness distillation, which we study for decision tree complexity but can be considered for any complexity measure: for a function that requires large decision trees, we give a general method for identifying a small set of inputs that is responsible for its complexity. Our technique even rules out query learners that are allowed constant error. This contrasts with existing lower bounds for the setting of random examples which only hold for inverse-polynomial error. Joint work with Caleb Koch and Carmen Strassle.
3:30 - 4:00 Sophie Yu (Duke) Random graph matching at Otter's tree-counting threshold via counting chandeliers[Abstract]
Given a pair of graphs, the problem of graph matching or network alignment refers to finding the underlying vertex correspondence that maximally aligns the edges. This is a ubiquitous problem arising in a variety of applications across diverse fields such as network privacy, computational biology, computer vision, and natural language processing. Graph matching is an instance of the notoriously difficult quadratic assignment problem (QAP), which is NP-hard to solve or approximate. Despite the worst-case computational hardness of QAP, I will present a computationally efficient graph matching algorithm based on counting a special family of trees. When the two networks are Erdős–Rényi random graphs with correlated edges through the hidden vertex correspondence, we show that our algorithm correctly matches all but a vanishing fraction of vertices with high probability as soon as the edge correlation exceeds the square root of Otter's constant. Moreover, we further upgrade the almost exact recovery to exact recovery whenever it is information-theoretically possible. This is the first polynomial-time algorithm that achieves exact and almost exact matching with an explicit constant correlation for both dense and sparse graphs.

Day 3: Friday, June 16, 2023

Time (EDT) Speaker Title
9:30 - 10:00 Coffee and snacks
10:00 - 10:45 Joan Bruna (NYU) TBD[Abstract]
10:45 - 11:30 Dana Yang (Cornell) TBD[Abstract]
11:30 - 12:00 Frederic Koehler (Stanford) TBD[Abstract]
12:00 - 2:00 Lunch Break
2:00 - 2:30 Brice Huang (MIT) Algorithmic Threshold for Multi-Species Spherical Spin Glasses[Abstract]
This talk focuses on optimizing the random and non-convex Hamiltonians of spherical spin glasses with multiple species. Our main result gives a variational formula for the best possible value ALG achievable by class of Lipschitz algorithms and gives a matching algorithm in this class based on approximate message passing. Our hardness result is proved using the Branching OGP introduced in our previous work [H-Sellke 21] to identify ALG for single-species spin glasses. This and all other OGPs for spin glasses have been proved using Guerra's interpolation method. We introduce a new method to prove the Branching OGP which is both simpler and more robust. It works even for models in which the true maximum value of the objective function remains unknown. Based on joint work with Mark Sellke.
2:30 - 3:15 Aravindan Vijayraghavan (Northwestern) Finding planted elements in linear sections of varieties[Abstract]
We consider a class of algorithmic problems about finding elements in the intersection of a given algebraic variety with a given linear subspace. This has connections to important questions in quantum information theory and tensor decompositions, even in the special case when the variety is the set of rank-1 matrices. I will introduce a natural planted setting of this problem that captures "generic" instances of the problem. I will then describe new polynomial time algorithms along with their implications in certain parameter regimes, and also highlight some open questions. This is based on joint work with Nathaniel Johnston and Benjamin Lovitz.
3:15 - 4:00 Greg Valiant (Stanford) Optimization with Limited Memory?[Abstract]
In many high-dimensional optimization settings, there are significant gaps between the amount of data or number of iterations required by algorithms whose memory usage scales linearly with the dimension versus more complex and memory-intensive algorithms. Do some problems inherently require super-linear (or quadratic memory) to be solved efficiently? In this talk, we will survey the lay-of-the-land of fundamental tradeoffs between the amount of available memory, and the amount of data or queries to the function being optimized. This will include a discussion of our work showing that for optimizing a convex function, given the ability to query the function value/gradient at points, a significantly super-linear amount of memory is required to achieve the optimal rate of convergence obtained by algorithms using more than quadratic memory. Throughout, we will emphasize the many open problems in this area.

See also the 2021 FODSI workshop on ML 4 Algorithms here and 2022 FODSI workshop on sublinear algorithms here.