Скачать или смотреть (Arguably) Hard on Average Optimization Problems and the Overlap Gap Property

By David Gamarnik (MIT)
Abstract: Many problems in the area of random combinatorial structures and high-dimensional statistics exhibit an apparent computational hardness, even though the formal results establishing such hardness is lacking. Examples include the problem of finding an independent set of a random graph, finding a proper coloring of a random graph and the problem of finding the largest submatrix of a random matrix.
Inspired by insights from the statistical physics we propose a general conjecture regarding the onset of hardness for these type of problems formulated in terms of a certain overlap gap property. We conjecture that such problems become hard on average when the space of overlaps becomes disconnected in an appropriate sense (the model exhibits an overlap gap), and we prove the existence of such gaps for several of these problems including the problem of finding the largest submatrix of a random Gaussian matrix. Furthermore, we establish that the overlap gap property is a provable obstacle for a certain class of local algorithms for the problem of finding a largest independent set of a sparse graph and finding a satisfying assignment of a random NAE-K-SAT problem.
Joint work with Madhu Sudan and Quan Li.