BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CMSA - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CMSA
X-ORIGINAL-URL:https://cmsa.fas.harvard.edu
X-WR-CALDESC:Events for CMSA
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20220313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20221106T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20230312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20231105T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20230208T123000
DTEND;TZID=America/New_York:20230208T133000
DTSTAMP:20260407T165534
CREATED:20230817T175326Z
LAST-MODIFIED:20240214T112702Z
UID:10001273-1675859400-1675863000@cmsa.fas.harvard.edu
SUMMARY:From spin glasses to Boolean circuits lower bounds - Algorithmic barriers from the overlap gap property
DESCRIPTION:Speaker: David Gamarnik (MIT) \nTitle: From spin glasses to Boolean circuits lower bounds. Algorithmic barriers from the overlap gap property \nAbstract: Many decision and optimization problems over random structures exhibit an apparent gap between the existentially optimal values and algorithmically achievable values. Examples include the problem of finding a largest independent set in a random graph\, the problem of finding a near ground state in a spin glass model\, the problem of finding a satisfying assignment in a random constraint satisfaction problem\, and many many more. Unfortunately\, at the same time no formal computational hardness results exist which  explains this persistent algorithmic gap. \nIn the talk we will describe a new approach for establishing an algorithmic intractability for these problems called the overlap gap property. Originating in statistical physics theory of spin glasses\, this is a simple to describe property which a) emerges in most models known to exhibit an apparent algorithmic hardness; b) is consistent with the hardness/tractability phase transition for many models analyzed to the day; and\, importantly\, c) allows to mathematically rigorously rule out a large class of algorithms as potential contenders\, specifically the algorithms which exhibit a form of stability/noise insensitivity. \nWe will specifically show how to use this property to obtain stronger (stretched exponential) than the state of the art (quasi-polynomial) lower bounds on the size of constant depth Boolean circuits for solving the two of the aforementioned problems: the problem of finding a large independent set in a sparse random graph\, and the problem of finding a near ground state of a p-spin model. \nJoint work with Aukosh Jagannath and Alex Wein
URL:https://cmsa.fas.harvard.edu/event/collquium-2823/
LOCATION:CMSA Room G10\, CMSA\, 20 Garden Street\, Cambridge\, MA\, 02138\, United States
CATEGORIES:Colloquium
ATTACH;FMTTYPE=image/png:https://cmsa.fas.harvard.edu/media/02CMSA-Colloquium-02.08.2023.png
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20230208T153000
DTEND;TZID=America/New_York:20230208T163000
DTSTAMP:20260407T165534
CREATED:20230807T170441Z
LAST-MODIFIED:20240228T112614Z
UID:10001188-1675870200-1675873800@cmsa.fas.harvard.edu
SUMMARY:Bakry-Emery theory and renormalisation
DESCRIPTION:Probability Seminar \nSpeaker: Roland Bauerschmidt (Cambridge)\n\nTitle: Bakry-Emery theory and renormalisation \nAbstract: I will discuss an approach to log-Sobolev inequalities that\ncombines the Bakry-Emery theory with renormalisation and present several\napplications. These include log-Sobolev inequalities with polynomial\ndependence for critical Ising models on Z^d when d>4 and singular SPDEs\nwith uniform dependence of the log-Sobolev constant on both the\nregularisation and the volume. The talk is based on joint works with\nThierry Bodineau and Benoit Dagallier.
URL:https://cmsa.fas.harvard.edu/event/probability-2823/
LOCATION:Hybrid
CATEGORIES:Probability Seminar
ATTACH;FMTTYPE=image/png:https://cmsa.fas.harvard.edu/media/CMSA-Probability-Seminar-02.08.23.png
END:VEVENT
END:VCALENDAR