Eden Chlamtac

We introduce a framework for studying semidefinite programming (SDP) relaxations based on the Lasserre hierarchy in the context of approximation algorithms for combinatorial problems. As an application of our approach we give improved approximation algorithms for two problems. We show that for some fixed constant ε > 0, given a 3-uniform hypergraph containing an independent set of size (1/2 - ε)n, we can find an independent set of size Ω(nε). This improves upon the result of Krivelevich, Nathaniel and Sudakov, who gave an algorithm finding an independent set of size Ω̃(n^6γ-3) for hypergraphs with an independent set of size γn (but no guarantee for γ ≤ 1/2). We also give an algorithm which finds an O(n^0.2072)-coloring given a 3-colorable graph, improving upon the work of Arora, Chlamtac and Charikar. Our approach stands in contrast to a long series of inapproximability results in the Lovász Schrijver linear programming (LP) and SDP hierarchies for other problems.