ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-017 | 23rd January 2013 20:12

A Short Excursion into Semi-Algebraic Hierarchies

RSS-Feed




TR13-017
Authors: Pratik Worah
Publication: 25th January 2013 16:05
Downloads: 581
Keywords: 


Abstract:

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 systems (cf. Grigoriev et al.).



ISSN 1433-8092 | Imprint