[Sds-seminars] Afonso Bandeira speaking in Discrete Math Seminar Wednesday Feb 20

[Dan Spielman]

This Combinatorics seminar should be of interest to some of you.

  --Dan


*Speaker:*  Afonso Bandeira (Courant Institute - NYU)
*Title:*  Optimizing and certifying bounds of random functions over the
hypercube
*Wednesday Feb 20 starting at 4pm in LOM 200*.

*Abstract:*

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20190218/186f2252/attachment.html>