BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:David Gamarnik (MIT) DTSTART:20200413T130000Z DTEND:20200413T140000Z DTSTAMP:20260423T035409Z UID:EPC/1 DESCRIPTION:Title: Over lap gap property: a provable barrier to fast optimization in probabilistic combinatorial structures\nby David Gamarnik (MIT) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nMany combinatorial optimization problems defined on random instances\, such as random graphs \, exhibit an apparent gap between the optimal values\, which can be compu ted by non-constructive means\, and the best values achievable by fast (po lynomial time) algorithms. Through a combined effort of mathematicians\, c omputer scientists and statistical physicists\, it became apparent that a potential\, and in some cases\, a provable barrier for designing fast algo rithms bridging this gap is an intricate topology of nearly optimal soluti ons\, in particular the presence of a certain Overlap Gap Property (OGP)\, which we will introduce in this talk. We will demonstrate how for many su ch problems the onset of the OGP phase transition indeed nearly coincides with algorithmically hard regimes and provides a provable barrier to a bro ad class of polynomial time algorithms. Our examples will include the prob lem of finding a largest independent set of a random graph\, finding a lar gest cut in a random hypergraph\, the problem of finding a ground state of a p-spin model\, and also many models in high-dimensional statistics and machine learning fields. The classes of algorithms ruled out by the OGP in clude local algorithms\, Markov Chain Monte Carlo\, Approximate Message Pa ssing and low-degree polynomial based algorithms.\n\nJoint work with Madhu Sudan\, Wei-Cuo Chen\, Dmitry Panchenko\, Mustazee Rahman\, Aukosh Jagann ath and Alex Wein.\n LOCATION:https://researchseminars.org/talk/EPC/1/ END:VEVENT END:VCALENDAR