Explicit optimization lower bounds from topological expansion

Abstract: I will explain a recent construction of explicit instances of optimization problems, which are hard for the family of optimization algorithms captured by so called “sum-of-squares” (SoS) hierarchy of semidefinite programs. The SoS hierarchy is a powerful family of algorithms, which captures many known optimization and approximation algorithms. Several constructions of random families of instances have been proved to be hard for these algorithms, in the literature on optimization and proof complexity (since the duals of these optimization algorithms can be viewed as proof systems). I will describe a recent construction, based on the Ramanujan 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).

Joint work with Irit Dinur, Yuval Filmus, and Prahladh Harsha.

differential geometrygeometric topologymetric geometry

Audience: researchers in the topic

Topology and geometry: extremal and typical

Series comments: Sign up for the mailing list groups.google.com/g/tget-seminar to receive zoom links.