EXTENSION COMPLEXITY OF INDEPENDENT SET POLYTOPES
EXTENSION COMPLEXITY OF INDEPENDENT SET POLYTOPES
复制标题
DOI：
10.1137/16m109884x
复制
发表时间：
2018-01-01
影响因子：
1.6
通讯作者：
Watson, Thomas
中科院分区：
文献类型：
--
作者：
Goeoes, Mika;Jain, Rahul;Watson, Thomas
我们展示了一个N节点图，其独立的集合需要在Omega中的尺寸指数的扩展公式（N/log N）。以前，尚无明确的n维0/1- polytopes的示例，其扩展复杂度大于theta（root n）中的指数大。我们的构造灵感来自扩展配方与（单调）电路深度之间相对鲜为人知的连接。
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 (root n). Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth.