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”.
https://arxiv.org/abs/2205.02319
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
