Revision #1 Authors: Mika Göös, Rahul Jain, Thomas Watson

Accepted on: 10th February 2018 22:12

Downloads: 525

Keywords:

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.

TR16-070 Authors: Mika Göös, Rahul Jain, Thomas Watson

Publication: 28th April 2016 14:17

Downloads: 1572

Keywords:

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.