EVENT DETAILS AND ABSTRACT

Title: Low-Degree Hardness of Random Optimization Problems
Speaker: Alex Wein
Speaker Info: Simons Institute
Brief Description:
Special Note:
Abstract:

I will consider random optimization problems, including the problem of finding a large independent set in a random graph, and the problem of optimizing the Hamiltonian of mean-field spin glass models. These problems often have a gap between the globally-optimal objective value and the objective value achievable by any known polynomial-time algorithm. To provide concrete evidence that this computational hardness is inherent, we prove that the class of "low-degree polynomial algorithms" fails to surpass a particular objective value. This class of algorithms is quite powerful in that it captures many of the best known algorithms for these types of problems, including approximate message passing and local algorithms (factor of i.i.d.). The proof involves a variant of the so-called "overlap gap property," which is a structural property of the solution space. Using similar techniques, we can also prove lower bounds against low-depth Boolean circuits.