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.
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.





![In Search of Missing Mass: Disentangling Discoveries from Hallucinations
Eric Nalisnick (Johns Hopkins University)
https://simons.berkeley.edu/talks/eric-nalisnick-johns-hopkins-university-2026-10-07
Trustworthy AI: From Hallucinations to Reliable Autonomy
Large language models (LLMs) hold much promise for scientific discovery. However, many basic questions remain about when an LLM can reliably make discoveries. In this talk, I will discuss how to interpret and extend the hallucination results of Kalai & Vempala [STOC 2024] to characterize an LLMs potential for discovery. In particular, how might we identify prompts that are likely to yield discoveries rather than hallucinations? In Search of Missing Mass: Disentangling Discoveries from Hallucinations](https://i.ytimg.com/vi/ZNlZsI9kBm4/mqdefault.jpg)




