Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The overlap gap property (OGP) is a powerful geometric framework for proving algorithmic lower bounds in random search and optimization problems. This framework has been used to show low degree lower bounds in problems including maximum independent set, random k-SAT, and the Ising perceptron, with several works showing that degree O(1) polynomial algorithms succeed with probability at most 1− Ω(1). We show a strengthening of this lower bound: degree o(N) polynomials succeed with probability o(1). Our proof is based on a general-purpose enhancement of the ensemble OGP, which can be used to upgrade existing algorithmic barriers in a black-box way. The bounds we obtain are sharp assuming a version of the low degree conjecture, and suggest a general heuristic for translating an OGP into a running time lower bound in random search problems. Based on joint work with Mark Sellke.