Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-070 | 10th February 2018 22:12

Extension Complexity of Independent Set Polytopes

RSS-Feed




Revision #1
Authors: Mika Göös, Rahul Jain, Thomas Watson
Accepted on: 10th February 2018 22:12
Downloads: 794
Keywords: 


Abstract:

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.


Paper:

TR16-070 | 24th April 2016 17:52

Extension Complexity of Independent Set Polytopes





TR16-070
Authors: Mika Göös, Rahul Jain, Thomas Watson
Publication: 28th April 2016 14:17
Downloads: 2001
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint