Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics. (arXiv:2004.12063v2 [cs.CC] UPDATED)

Web: http://arxiv.org/abs/2004.12063

We consider the problem of finding nearly optimal solutions of optimization
problems with random objective functions. Two concrete problems we consider are
(a) optimizing the Hamiltonian of a spherical or Ising $p$-spin glass model,
and (b) finding a large independent set in a sparse Erd\H{o}s-R\'{e}nyi graph.
The following families of algorithms are considered: (a) low-degree polynomials
of the input; (b) low-depth Boolean circuits; (c) the Langevin dynamics
algorithm. We show that these families of algorithms fail to produce nearly
optimal …

arxiv optimization random