ARC Colloquium: Dylan Altschuler (NYU)

Algorithms & Randomness Center (ARC)

Dylan Altschuler (NYU)

January 30, 2023

Klaus 1116 - 11:00 am

Title: The critical window of the symmetric perceptron

Abstract:  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”. 


Speaker's Webpage

Videos of recent talks are available at: and

Click here to subscribe to the seminar email list:

Event Details


  • Monday, January 30, 2023
    11:00 am - 12:00 pm