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, MikaJain, Rahul Watson, Thomas Keywords: cs.CCcs.CCcs.DMmath.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 PublicationsElements

###### Files in This Item:
File Description SizeFormatAccess SettingsVersion
1604.07062v1.pdf912.37 kBAdobe PDF

OPEN

Post-print

#### 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

Check

#### Altmetric

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