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:20260404T143403Z UID:EPC/1 DESCRIPTION:Title: Overlap gap property: a provable barrier to fast optimization in probab ilistic combinatorial structures\nby David Gamarnik (MIT) as part of E xtremal and probabilistic combinatorics webinar\n\n\nAbstract\nMany combin atorial optimization problems defined on random instances\, such as random graphs\, exhibit an apparent gap between the optimal values\, which can b e computed by non-constructive means\, and the best values achievable by f ast (polynomial time) algorithms. Through a combined effort of mathematici ans\, computer scientists and statistical physicists\, it became apparent that a potential\, and in some cases\, a provable barrier for designing fa st algorithms bridging this gap is an intricate topology of nearly optimal solutions\, in particular the presence of a certain Overlap Gap Property (OGP)\, which we will introduce in this talk. We will demonstrate how for many such problems the onset of the OGP phase transition indeed nearly coi ncides with algorithmically hard regimes and provides a provable barrier t o a broad class of polynomial time algorithms. Our examples will include t he problem of finding a largest independent set of a random graph\, findin g a largest cut in a random hypergraph\, the problem of finding a ground s tate of a p-spin model\, and also many models in high-dimensional statisti cs and machine learning fields. The classes of algorithms ruled out by the OGP include local algorithms\, Markov Chain Monte Carlo\, Approximate Mes sage Passing and low-degree polynomial based algorithms.\n\nJoint work wit h Madhu Sudan\, Wei-Cuo Chen\, Dmitry Panchenko\, Mustazee Rahman\, Aukosh Jagannath and Alex Wein.\n LOCATION:https://stable.researchseminars.org/talk/EPC/1/ END:VEVENT END:VCALENDAR