Loading jsMath...
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