Duration: 56:25

731 views

18

Semidefinite programming (SDP) is one of the most powerful general purpose methods in combinatorial optimization, and understanding its strengths and limitations is a central focus of research in mathematical optimization. In joint work with Raghavendra and Steurer, we showed recently that polytopes associated to NP-hard problems (like Max-Cut and the Traveling Salesman Problem) do not admit SDP characterizations of subexponential size. Previously, it was unclear how to achieve such strong lower bounds for any explicit family of polytopes. A key insight involves associating a large quantum-classical state to an SDP and then learning a “simple” approximation to that state via a boosting process guided by the von Neumann entropy. The idea of viewing certain kinds of classical objects as points in a relaxed quantum landscape has other potential applications in the theory of computation.
Resources: Following are some blog entries about entropy optimization, lifts of polytopes, and related things.
Arxiv pointer to the main reference:
https://arxiv.org/abs/1411.6317

Matrix scaling (https://tcsmath.org/2015/06/16/entropy-optimality-matrix-scaling/)
Chang’s Lemma (https://tcsmath.org/2015/06/17/entropy-optimality-changs-lemma/)
A potential function (https://tcsmath.org/2015/06/17/entropy-optimality-a-potential-function/)
Bloom’s Chang’s Lemma (https://tcsmath.org/2015/06/18/entropy-optimality-blooms-changs-lemma/)
Forster’s isotropy (https://tcsmath.org/2015/06/19/entropy-optimality-forsters-isotropy/)
Primer: Lifts of polytopes (https://tcsmath.org/2015/06/20/primer-lifts-of-polytopes-and-non-negative-matrix-factorization/)
Lifts of polytopes (https://tcsmath.org/2015/06/21/entropy-optimality-lifts-of-polytopes/)
Non-negative rank (https://tcsmath.org/2015/06/23/entropy-optimality-non-negative-rank-lower-bounds/)
Quantum lifts (https://tcsmath.org/2015/06/29/entropy-optimality-quantum-lifts-of-polytopes/)
Analytic PSD rank (https://tcsmath.org/2015/07/04/entropy-optimality-analytic-psd-rank-and-johns-theorem/)
HIM Lecture notes (https://tcsmath.org/2015/09/18/lecture-notes-for-the-summer-school-on-combinatorial-optimization-at-him/)
Optimality on path spaces (https://tcsmath.org/2015/11/16/entropy-optimality-on-path-space/)
Follmer drift and log-Sobolev (https://tcsmath.org/2015/11/21/follmers-drift-itos-lemma-and-the-log-sobolev-inequality/)