[Statlist] IFOR-Talk: Tim Kunisky, Friday, November 15, 2019

[Kaiser-Heinzmann Susanne]

Institute for Operations Research, ETH Zürich:

We are pleased to inform you of the next IFOR talk:

Date: Friday, November 15, 2019
Time: 13:00 hrs
Room: HG G 19.2, ETH Zurich

Speaker: Tim Kunisky, Courant Institute of Mathematical Sciences at New York University, USA

Title: Hardness of certification for random quadratic programming problems

Abstract:  I will describe recent results on the computational cost of certifying bounds on Gaussian random instances of a class of quadratic optimization problems. Unlike merely finding good feasible points, certification demands an easy-​to-verify proof (like that furnished by the sum-​of-squares hierarchy) of a bound on the objective function. I will present several forms of evidence that certifying bounds can be significantly harder than searching for good feasible points. First, I will show how to adapt the heuristic “low-​degree method” for assessing the computational hardness of hypothesis testing problems to also suggest hardness of certification. Second, time permitting, I will outline a more concrete result confirming that the degree 4 sum-​of-squares algorithm fails to certify tight bounds for a specific well-​studied problem, that of optimizing the Hamiltonian of the Sherrington-​Kirkpatrick model from statistical physics. (Based on joint work with Afonso Bandeira and Alex Wein.)

Feel free to forward the announcement to anyone who might be interested in the seminar.

*******************************************
ETH Zurich
Annette Ryter
Department of Mathematics
Institute for Operations Research
HG G 21.4
Raemistrasse 101 
8092 Zurich, Switzerland

Phone +41 44 632 40 16
annette.ryter using ifor.math.ethz.ch
www.math.ethz.ch/ifor
*******************************************