We consider the problem of certifying an upper bound on the maximum value of a random quadratic form over the hypercube, which corresponds to the problem of optimizing the Hamiltonian of the Sherrington-Kirkpatrick model of statistical physics. We will show that, conditional on the “low-degree polynomials conjecture” concerning the computational hardness of random problems, there is no polynomial-time algorithm certifying a better upper bound than the largest eigenvalue of the coefficient matrix. If time permits we will discuss connections to optimization in random graphs.
Optimizing and certifying bounds of random functions over the hypercube
Wednesday, March 6, 2019 - 4:00pm
Courant Institute - NYU
There are two discrete math talk this week. This talk is at an atypical meeting time and location