On Zeros and Algorithms for Disordered Systems @SimonsInstitute
On Zeros and Algorithms for Disordered Systems  @SimonsInstitute
Uploaded October 2026 | Updated November 2026, 3 days ago
Kuikui Liu (MIT)
https://simons.berkeley.edu/talks/kuikui-liu-mit-2026-10-13
Probabilistic Phenomena on Graphs, Groups, and Manifolds

Counting and sampling are fundamental algorithmic primitives in high-dimensional statistics and computer science. For many models, there is an enormous literature studying the worst-case computational complexity of these tasks and how they connect to phase transitions the underlying system undergoes as its parameters (e.g., ""temperature"") are varied. Their average-case complexity is comparatively far less understood.

We study the problem of estimating the partition function of Ising models with random interactions. These are fundamental probability distributions originating in statistical physics that form a useful sandbox for new algorithms and mathematical techniques. We give the first QPTAS for the Sherrington-Kirkpatrick model and the first FPTAS for the antiferromagnetic Ising model on the uniformly random d-regular graph, for all inverse temperatures up to their respective replica symmetry breaking thresholds; beyond these thresholds, it is believed that no such algorithms exist. To achieve these results, we study the locations of the zeros of the partition function, drawing inspiration from the seminal Lee-Yang program. More specifically, we establish the absence of Fishers zeros via a combination of Jensen's Formula, the second moment method, and small subgraph conditioning.

Joint work with Ferenc Bencs, Brice Huang, Daniel Z. Lee, and Guus Regts.
On Zeros and Algorithms for Disordered SystemsSymmetric Self-Dual Quantum Codes on High Dimensional Expanders with Single-Orbit Low-Weight ChecksOptimal Inference Schedules for Masked Diffusion ModelsFinite-particles rates for drifting modelsOn the interplay of accuracy and fairness in computational healthcareRecovering Riemannian metric distance from Random Geometric GraphsIn Search of Missing Mass: Disentangling Discoveries from HallucinationsExplicit lossless vertex expandersQuantum ergodicity on graphs (Part 2)Convex-body Sampling to the Kannan-Lovász-Simonovits ConjectureBuilding a Quantum Computer with QLDPC CodesSampling elements of a finite group: efficiency of the product replacement algorithm with...
Simons Institute for the Theory of Computing |

On Zeros and Algorithms for Disordered Systems

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER