Séminaire quantique

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

## by Guillaume Aubrun

Europe/Paris
salle du conseil du LIP (ENS Lyon)

### salle du conseil du LIP

#### ENS Lyon

Description

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