*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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
