Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with extended formulations:
TR12-131 | 18th October 2012
Mark Braverman, Ankur Moitra

An Information Complexity Approach to Extended Formulations

Revisions: 1

We prove an unconditional lower bound that any linear program that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. There has been considerable recent interest in proving unconditional lower bounds against any linear program. Fiorini et al proved that there is no polynomial sized linear program for traveling salesman. ... more >>>

TR16-070 | 24th April 2016
Mika Göös, Rahul Jain, Thomas Watson

Extension Complexity of Independent Set Polytopes

Revisions: 1

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 ... more >>>

TR16-117 | 31st July 2016
Mrinalkanti Ghosh, Madhur Tulsiani

From Weak to Strong LP Gaps for all CSPs

Revisions: 1

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by $\Omega\left(\frac{\log n}{\log \log n}\right)$ levels of the Sherali-Adams hierarchy on instances ... more >>>

TR17-185 | 28th November 2017
Makrand Sinha

Lower Bounds for Approximating the Matching Polytope

We prove that any extended formulation that approximates the matching polytope on $n$-vertex graphs up to a factor of $(1+\varepsilon)$ for any $\frac2n \le \varepsilon \le 1$ must have at least ${n}\choose{{\alpha}/{\varepsilon}}$ defining inequalities where $0<\alpha<1$ is an absolute constant. This is tight as exhibited by the $(1+\varepsilon)$ approximating linear ... more >>>

TR22-003 | 4th January 2022
Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

On Semi-Algebraic Proofs and Algorithms

Revisions: 1

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$ Sherali-Adams refutation of an unsatisfiable CNF formula $C$ if and only if there is an $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts ... more >>>

ISSN 1433-8092 | Imprint