Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Semidefinite Programs:
TR01-042 | 31st May 2001
Marek Karpinski

Approximating Bounded Degree Instances of NP-Hard Problems

We present some of the recent results on computational complexity
of approximating bounded degree combinatorial optimization problems. In
particular, we present the best up to now known explicit nonapproximability
bounds on the very small degree optimization problems which are of
particular importance on the intermediate stages ... more >>>

TR13-017 | 23rd January 2013
Pratik Worah

A Short Excursion into Semi-Algebraic Hierarchies

This brief survey gives a (roughly) self-contained overview of some complexity theoretic results about semi-algebraic proof systems and related hierarchies and the strong connections between them. The article is not intended to be a detailed survey on "Lift and Project" type optimization hierarchies (cf. Chlamtac and Tulsiani) or related proof ... more >>>

ISSN 1433-8092 | Imprint