Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Critical window of the symmetric perceptron

Probability

Speaker: Dylan Altschuler, Courant Institute, NYU
Related Webpage: https://arxiv.org/abs/2205.02319
Location: 2112 MSB / Zoom
Start time: Tue, Sep 27 2022, 1:10PM

We study a random constraint satisfaction problem called the symmetric binary perceptron (SBP). The SBP is a well-studied model in statistical physics, and also can be viewed as a random analogue of the celebrated theory of combinatorial discrepancy. Our goal is to characterize the “critical window” of the SBP. Namely, how many constraints do we need to add for the probability of satisfiability to drop from .99 to .01?

Our main result is that the satisfiability transition of the SBP corresponds to the addition of only a constant number of clauses. This is essentially the sharpest possible transition. Our result adds the SBP to a short list of random satisfaction problems for which the critical window is rigorously known to be this small. Interestingly, the critical window of the SBP is far smaller than standard techniques would suggest, a phenomenon known as “superconcentration”.