BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Madhur Tulsiani (TTIC) DTSTART:20210419T160000Z DTEND:20210419T170000Z DTSTAMP:20260423T053140Z UID:TG_ET/17 DESCRIPTION:Title: E xplicit optimization lower bounds from topological expansion\nby Madhu r Tulsiani (TTIC) as part of Topology and geometry: extremal and typical\n \n\nAbstract\nI will explain a recent construction of explicit instances o f optimization problems\, which are hard for the family of optimization al gorithms captured by so called “sum-of-squares” (SoS) hierarchy of sem idefinite programs. The SoS hierarchy is a powerful family of algorithms\, which captures many known optimization and approximation algorithms. Seve ral constructions of random families of instances have been proved to be h ard for these algorithms\, in the literature on optimization and proof com plexity (since the duals of these optimization algorithms can be viewed as proof systems). I will describe a recent construction\, based on the Rama nujan complexes of Samuels\, Lubotzky and Vishne\, which yields the first explicit family instances\, where the optimization problem is hard even to solve approximately (using SoS).\n\nJoint work with Irit Dinur\, Yuval Fi lmus\, and Prahladh Harsha.\n LOCATION:https://researchseminars.org/talk/TG_ET/17/ END:VEVENT END:VCALENDAR