Optimizing and certifying bounds of random functions over the hypercube

Seminar: 
Combinatorics Seminar
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