עדן כלמטץ'

For every fixed γ ≥ 0, we give an algorithm that, given an n-vertex 3-uniform hypergraph containing an independent set of size γn, finds an independent set of size . This improves upon a recent result of Chlamtac, which, for a fixed ε > 0, finds an independent set of size n ^ε in any 3-uniform hypergraph containing an independent set of size . The main feature of this algorithm is that, for fixed γ, it uses the Θ(1/γ ²)-level of a hierarchy of semidefinite programming (SDP) relaxations. On the other hand, we show that for at least one hierarchy which gives such a guarantee, 1/γ levels yield no non-trivial guarantee. Thus, this is a first SDP-based algorithm for which the approximation guarantee improves indefinitely as one uses progressively higher-level relaxations.