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: | MSB 2112 / 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”.