![Bridging Continuous and Discrete Optimization_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Bridging%20Continuous%20and%20Discrete%20Optimization_hi-res.png.jpg?itok=b7fmT0eV)
Abstract
I will discuss a recent exponential-in-Omega(n/log(n)) lower bound on the extension complexity of independent set polytopes. This result is inspired by "query-to-communication lifting" theorems, as well as a connection between extended formulations and (monotone) circuit complexity.
Joint work with Rahul Jain and Thomas Watson.