Wednesday, March 6, 2019
03/06/2019 - 4:00pm
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.
03/06/2019 - 4:15pm
This talk will be about the analogy between functions and spaces and exporting back and forth constructions that seem more natural in one setting or the other. Among the players are interpolation, entropy, persistent homology, and variational problems. The ultimate goal is to shed some light on the geometry of nonlinear function spaces, and use this to understand the complexity of the solutions of classical topological problems.