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