Seminar Details
2021-03-09 (14h) : Polyhedral approximations of the positive semidefinite cone
At MS Teams
Organized by Mathematical Engineering
Speaker :
Hamza Fawzi (University of Cambridge, UK)
Abstract :
LP solvers are more efficient than SDP ones and can scale to much larger problem sizes. A natural question is: how well can we approximate SDPs using LPs? In this talk I will discuss a hardness result showing that any "reasonable" approximation of the nxn positive semidefinite cone, must have extension complexity that is at least superpolynomial in n. The proof uses tools from Fourier analysis which I will present in the talk. Based on arXiv:1811.09649.