Talks
Fall 2017
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/opt7large-01.png?itok=MmjWP0n3)
Independent Set Polytopes: Query vs. Communication Perspective
Wednesday, November 8th, 2017, 2:30 pm–3:30 pm
Speaker:
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.