Event time:
Wednesday, March 6, 2019 - 4:00pm
Location:
LOM 200
Speaker:
Afonso Bandeira
Speaker affiliation:
Courant Institute - NYU
Event description:
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.
Research Area(s):
Special note:
There are two discrete math talk this week. This talk is at an atypical meeting time and location