BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Extension Complexity of Independent Set Polytopes Göös, Mika


We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth. Joint work with Rahul Jain and Thomas Watson.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International