Please use this identifier to cite or link to this item:
https://doi.org/10.1109/focs.2016.67
DC Field | Value | |
---|---|---|
dc.title | Extension Complexity of Independent Set Polytopes | |
dc.contributor.author | Goos, Mika | |
dc.contributor.author | Jain, Rahul | |
dc.contributor.author | Watson, Thomas | |
dc.date.accessioned | 2019-07-16T09:12:58Z | |
dc.date.available | 2019-07-16T09:12:58Z | |
dc.date.issued | 2016-10 | |
dc.identifier.citation | Goos, Mika, Jain, Rahul, Watson, Thomas (2016-10). Extension Complexity of Independent Set Polytopes. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) 23 : 70-70. ScholarBank@NUS Repository. https://doi.org/10.1109/focs.2016.67 | |
dc.identifier.uri | https://scholarbank.nus.edu.sg/handle/10635/156683 | |
dc.description.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. | |
dc.publisher | IEEE | |
dc.source | Elements | |
dc.subject | cs.CC | |
dc.subject | cs.CC | |
dc.subject | cs.DM | |
dc.subject | math.CO | |
dc.type | Article | |
dc.date.updated | 2019-07-16T09:09:43Z | |
dc.contributor.department | DEPT OF COMPUTER SCIENCE | |
dc.description.doi | 10.1109/focs.2016.67 | |
dc.description.sourcetitle | 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) | |
dc.description.volume | 23 | |
dc.description.page | 70-70 | |
dc.published.state | Published | |
Appears in Collections: | Staff Publications Elements |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
1604.07062v1.pdf | 912.37 kB | Adobe PDF | OPEN | Post-print | View/Download |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.