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.