Optimizing and certifying bounds of random functions over the hypercube

Combinatorics Seminar
Event time: 
Wednesday, March 6, 2019 - 4:00pm
LOM 200
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