{"664894":{"#nid":"664894","#data":{"type":"event","title":"ARC Colloquium: Dylan Altschuler (NYU)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EDylan Altschuler\u0026nbsp;(NYU)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EJanuary 30, 2023\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E The critical window of the symmetric perceptron\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EWe study a random constraint satisfaction problem called the\u003Cem\u003E symmetric binary perceptron\u003C\/em\u003E (SBP). The SBP is closely related to long-standing conjectures in combinatorics and statistical physics. Our goal is to characterize the \u0026ldquo;critical window\u0026rdquo; of the SBP. Namely, how many constraints do we need to add for the probability of satisfiability to drop from .99 to .01?\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EOur 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 \u0026ldquo;superconcentration\u0026rdquo;.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/arxiv.org\/abs\/2205.02319\u0022 target=\u0022_blank\u0022\u003Ehttps:\/\/arxiv.org\/abs\/2205.02319\u003C\/a\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/dylanaltschuler.github.io\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003Cem\u003E and \u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E \u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The critical window of the symmetric perceptron - Klaus 1116 at 11:00 AM"}],"uid":"35702","created_gmt":"2023-01-19 13:36:37","changed_gmt":"2023-01-23 18:30:48","author":"mb121","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-01-30T11:00:00-05:00","event_time_end":"2023-01-30T12:00:00-05:00","event_time_end_last":"2023-01-30T12:00:00-05:00","gmt_time_start":"2023-01-30 16:00:00","gmt_time_end":"2023-01-30 17:00:00","gmt_time_end_last":"2023-01-30 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}