On pohyedral approximations of the positive semidefinite cone (after Hamza Fawzi)

par Guillaume Aubrun

mardi 14 janv. 2020, 11:30 → 13:00 Europe/Paris

salle du conseil du LIP (ENS Lyon)

We illustrate the fact that Semi Definite Programming is more powerful than Linear Programming by proving the following theorem: any polyhedral cone which approximates the cone of n x n positive matrices has extension complexity at least exp(c sqrt(n)). The proof uses notably the hypercontractivity inequality on the discrete cube. The talk will be self-contained. Reference: arXiv:1811.09649