Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GEOMETRIC PROOF SYSTEMS:
Reports tagged with Geometric Proof Systems:
TR12-003 | 13th December 2011
Pratik Worah

Rank Bounds for a Hierarchy of Lov\'{a}sz and Schrijver

Lov\'{a}sz and Schrijver introduced several lift and project methods for $0$-$1$ integer programs, now collectively known as Lov\'{a}sz-Schrijver ($LS$) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the $LS$ and $LS_+$ hierarchies. In this paper we investigate rank bounds in the ... more >>>




ISSN 1433-8092 | Imprint