Please use this identifier to cite or link to this item: https://doi.org/10.1109/focs.2016.67
Title: Extension Complexity of Independent Set Polytopes
Authors: Goos, Mika
Jain, Rahul 
Watson, Thomas
Keywords: cs.CC
cs.CC
cs.DM
math.CO
Issue Date: Oct-2016
Publisher: IEEE
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
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.
Source Title: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
URI: https://scholarbank.nus.edu.sg/handle/10635/156683
DOI: 10.1109/focs.2016.67
Appears in Collections:Staff Publications
Elements

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
1604.07062v1.pdf912.37 kBAdobe PDF

OPEN

Post-printView/Download

SCOPUSTM   
Citations

4
checked on Dec 6, 2019

Page view(s)

41
checked on Dec 5, 2019

Download(s)

1
checked on Dec 5, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.