Séminaire quantique

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

by Guillaume Aubrun

salle du conseil du LIP (ENS Lyon)

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