We discuss two algorithmic hardness results for the problem of optimizing in random structures. For both results we rule out  some classes of polynomial time algorithms  using the overlap gap property (OGP), which will be formalized in the talk.

The first one is the problem of optimizing a ground state of a spin glass model. The model is known to the exhibit the OGP, and in an earlier work we have used it to rule out algorithms based on low-degree polynomials. In this work, using similar techniques, we obtain lower bounds on the depth of boolean circuits for solving the same problem. We show that any poly-size circuit which finds a near ground state of an n-spin model has depth at least \log n/(3\log\log n), which interestingly improves the  state of the art circuit lower bounds for combinatorial optimization problems. Such known lower bounds are of the form o(log n/loglog n), obtained by Rossman for the clique problem. The results though are not directly comparable, as we require the circuit to solve the search as opposed to the decision problem. The bound is obtained by combining the OGP with Linial-Mansour-Nissan Theorem, which bounds Fourier coefficients for low-depth circuits.

The second problem is the Random Number Partitioning Problem (RNPP), which is the problem of splitting a set of n randomly weighted items into two groups with two sums as close as possible. When the weights are i.i.d. gaussians, the best partition achieves the difference of the two sums at most 2^{-n}, whereas the best known algorithm due to Karp and Karmarkar from 1980s achieves only value 2^{-O(\log^2 n)}. We show that the model exhibits the multioverlap version (to be defined)  of the OGP for the objective value bellow 2^{-f(n)} for some sublinear function f(n). This suffices to rule algorithms which exhibit low sensitivity to the input. The connection between the OGP and the failure of algorithms with low sensitivity is obtained by employing methods from the Ramsey theory in extremal combinatorics.

Joint work with Aukosh Jagannath, Alex Wein and Eren Kizildag