BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:David Gamarnik (MIT) DTSTART:20200422T140000Z DTEND:20200422T150000Z DTSTAMP:20260423T021030Z UID:MADPlus/3 DESCRIPTION:Title: Overlap gap property: a provable barrier to fast optimization in probabili stic combinatorial structures\nby David Gamarnik (MIT) as part of MAD+ \n\n\nAbstract\nMany combinatorial optimization problems defined on random instances exhibit an apparent gap between the optimal values\, which can be computed by non-constructive means\, and the best values achievable by fast (polynomial time) algorithms. Through a combined effort of mathematic ians\, computer scientists and statistical physicists\, it became apparent that a potential barrier for designing fast algorithms bridging this gap is an intricate topology of nearly optimal solutions\, in particular the p resence of the Overlap Gap Property (OGP)\, which we will introduce in thi s talk. We will discuss how for many such problems the onset of the OGP ph ase transition introduces indeed a provable barrier to a broad class of po lynomial time algorithms. Examples of such problems include the problem of finding a largest independent set of a random graph\, finding a largest c ut in a random hypergrah\, the problem of finding a ground state of a p-sp in model\, and also many problems in high-dimensional statistics field. In this talk we will demonstrate in particular why OGP is a barrier for thre e classes of algorithms designed to find a near ground state in p-spin mod els arising in the field of spin glass theory: Approximate Message Passing algorithms\, algorithms based on low-degree polynomial and Langevin dynam ics. Joint work with Aukosh Jagannath and Alex Wein\n LOCATION:https://researchseminars.org/talk/MADPlus/3/ END:VEVENT END:VCALENDAR