Student Probability Seminar

---

The critical window of the symmetric perceptron

Speaker: Dylan Altschuler, CIMS

Location: Warren Weaver Hall 1314

Date: Monday, April 3, 2023, 3 p.m.

Synopsis:

Abstract: We study sharp thresholds in a random combinatorial problem. Sharp thresholds are a fundamental phenomenon of high-dimensional random systems, and are subject of great interest in graph theory, statistical physics, etc. 

More specifically, we study a random constraint satisfaction problem called the symmetric binary perceptron (SBP). The SBP is closely related to long-standing conjectures in combinatorics and statistical physics. 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 a nearly constant number of clauses. This 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”.