researchseminars.org

Alex Wein (NYU)
2020-09-30 17:00 - 18:00 UTC | https://researchseminars.org/talk/TCSPlus/11/
Title: Low-Degree Hardness of Random Optimization Problems (https://researchseminars.org/talk/TCSPlus/11/)
by Alex Wein (NYU) as part of TCS+

Abstract
In high-dimensional statistical problems (including planted clique, sparse PCA, community detection, etc.), the class of "low-degree polynomial algorithms" captures many leading algorithmic paradigms such as spectral methods, approximate message passing, and local algorithms on sparse graphs. As such, lower bounds against low-degree algorithms constitute concrete evidence for average-case hardness of statistical problems. This method has been widely successful at explaining and predicting statistical-to-computational gaps in these settings.

While prior work has understood the power of low-degree algorithms for problems with a "planted" signal, we consider here the setting of "random optimization problems" (with no planted signal), including the problem of finding a large independent set in a random graph, as well as the problem of optimizing the Hamiltonian of mean-field spin glass models. I will define low-degree algorithms in this setting, argue that they capture the best known algorithms, and explain new proof techniques for giving lower bounds against low-degree algorithms in this setting. The proof involves a variant of the so-called "overlap gap property", which is a structural property of the solution space.

Based on joint work with David Gamarnik and Aukosh Jagannath, available at: https://arxiv.org/abs/2004.12063
