Kunal Marwaha, University of Chicago
We formalize a general and deep connection between two intensely studied classes of optimization problems: constraint satisfaction problems (CSPs), studied in computer science, and spin glass models, studied in statistical physics. We demonstrate that for dense enough random CSPs, the geometric properties of the set of nearly-optimal solutions converge to those of a corresponding spin glass model. In these spin glass models, the very same geometric properties imply bounds on the average-case approximability achieved by broad classes of algorithms; these bounds are conjectured to be the best possible among all polynomial-time algorithms. The correspondence we establish here implies that the same lower bounds apply to average-case CSPs. Joint work with Chris Jones, Juspreet Singh Sandhu, Jonathan Shi; https://arxiv.org/abs/2210.03006
Join via Zoom