ECCC-Report TR16-070https://eccc.weizmann.ac.il/report/2016/070Comments and Revisions published for TR16-070en-usSat, 10 Feb 2018 22:12:17 +0200
Revision 1
| Extension Complexity of Independent Set Polytopes |
Mika Göös,
Rahul Jain,
Thomas Watson
https://eccc.weizmann.ac.il/report/2016/070#revision1We 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.Sat, 10 Feb 2018 22:12:17 +0200https://eccc.weizmann.ac.il/report/2016/070#revision1
Paper TR16-070
| Extension Complexity of Independent Set Polytopes |
Mika Göös,
Rahul Jain,
Thomas Watson
https://eccc.weizmann.ac.il/report/2016/070We 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.Thu, 28 Apr 2016 14:17:54 +0300https://eccc.weizmann.ac.il/report/2016/070