BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Alex Wein (NYU)
DTSTART:20200930T170000Z
DTEND:20200930T180000Z
DTSTAMP:20260423T021010Z
UID:TCSPlus/11
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/11/"
 >Low-Degree Hardness of Random Optimization Problems</a>\nby Alex Wein (NY
 U) as part of TCS+\n\n\nAbstract\nIn high-dimensional statistical problems
  (including planted clique\, sparse PCA\, community detection\, etc.)\, th
 e class of "low-degree polynomial algorithms" captures many leading algori
 thmic paradigms such as spectral methods\, approximate message passing\, a
 nd local algorithms on sparse graphs. As such\, lower bounds against low-d
 egree algorithms constitute concrete evidence for average-case hardness of
  statistical problems. This method has been widely successful at explainin
 g and predicting statistical-to-computational gaps in these settings.\n\nW
 hile prior work has understood the power of low-degree algorithms for prob
 lems with a "planted" signal\, we consider here the setting of "random opt
 imization problems" (with no planted signal)\, including the problem of fi
 nding a large independent set in a random graph\, as well as the problem o
 f optimizing the Hamiltonian of mean-field spin glass models. I will defin
 e low-degree algorithms in this setting\, argue that they capture the best
  known algorithms\, and explain new proof techniques for giving lower boun
 ds against low-degree algorithms in this setting. The proof involves a var
 iant of the so-called "overlap gap property"\, which is a structural prope
 rty of the solution space.\n\nBased on joint work with David Gamarnik and 
 Aukosh Jagannath\, available at: https://arxiv.org/abs/2004.12063\n
LOCATION:https://researchseminars.org/talk/TCSPlus/11/
END:VEVENT
END:VCALENDAR