Computational complexity and phase transitions

24 September - 17 December 2026

Tursdays, 10:15 - 12:00

Location: HG G 19.1

First lecture: 24 September

Abstract

Like much of combinatorics and probability, statistical physics is concerned with asymptotics: the behavior of systems in the limit of large size. Spin glass theory in particular is interested in random structures. Finally, machine learning theory is interested in partly-random structures, where a “signal” is obscured by random noise. All three fields have beautiful connections with each other and with random graphs, random matrices, and random tensors, giving rise to a vibrant interdiscplinary community.

Over the past three decades, this community has uncovered the existence of phase transitions, where finding a signal in noisy data suddenly becomes impossible when the amount of noise exceeds a critical threshold — much like metals that lose their magnetic field at a critical temperature. For many problems there appears to be two distinct phase transitions, with a fascinating regime in between: where finding the signal is information-theoretically possible but computationally hard. This computational hardness is conjectural, but we can hope to prove that many of our favorite algorithms fail in this regime, including spectral algorithms, message-passing, Monte Carlo Markov chains, and so on.

These lectures will be broadly accessible. I’ll give an introduction to all of this from the point of view of a physicist who likes proving things when possible, and who is willing to make conjectures when not. Aspirationally, I’ll work towards some ongoing research, joint with Max Jerdee and Tim Kunisky, on free probability for random tensor networks, and the computatonal hardness of tensor PCA.

Here is a tentative list of topics. Each of these will 1-2 lectures depending on how they go.

Random graphs

• Sparse G(n,p) is treelike: short loops are rare
• The emergence and size of the giant component:
  - Proof by differential equations.
  - Proof by branching processes and extinction
• The k-core and recursive equations on trees

Random formulas

• Random k-SAT and the satisfiability threshold
• Upper bound: the first moment method
• Lower bound #1: algorithms and differential equations
• Lower bound #2: the second moment method
• The view from physics: clustering and condensation
• Easy, hard, and impossible

Networks and communities

• The stochastic block model
• Planted models and condensation: easy, hard, and impossible redux
• From Boltzmann to Bayes and back
• Ising models, free energies, variational methods, and KL divergence
• Belief propagation and the Kesten-Stigum threshold
• The non-backtracking operator

Random matrices, free probability, and phase transitions in PCA

• Gaussian matrices and the semicircle law
• The R-transform and spectral moments
• Random regular graphs and the Kesten-McKay distribution
• Rank-one perturbations of random matrices and the BBP transition

Tensor PCA and the Kikuchi matrix

• The tensor PCA problem
• Low-degree likelihood ratios and spectral algorithms
• Beyond belief: the Kikuchi free energy
• The Kikuchi matrix and its spectrum
• More applications of the Kikuchi matrix

Tensor networks, free cumulants, and Tensor PCA again

• Tensor networks and invariant polynomials
• Tensor cumulants and free additivity
• Low-degree likelihood redux
• Towards free probability for tensors