[Sds-seminars] CANCELLED: Afonso Bandeira Seminar Wednesday Feb 20

[Dan Spielman]

I have been told that this seminar has been cancelled due to weather.
It will be rescheduled for later in the semester.

  --Dan

On Mon, Feb 18, 2019 at 9:29 PM Dan Spielman <daniel.spielman at yale.edu>
wrote:

>
> 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/20190219/ab9d2446/attachment.html>