44 min
Seminar, Hosted by Simons Institute for the Theory of Computing
A computational phase transition for learning-to-sample from Ising models
UC San Diego
Recording
Abstract
Learning to generate new samples from an unknown Ising distribution exhibits a computational threshold determined by the interaction matrix's spectral width. Below the threshold, empirically initialized Glauber dynamics gives an efficient learner; just above it, a constructed family is cryptographically hard even with parameter access. The talk distinguishes sample generation from parameter estimation and studies a resulting memorization–hallucination trade-off.