Abstract
This talk shall focus on the problem of finding large independent sets in hypergraphs with certain useful structural properties. In particular, we shall describe tight inapproximability for independent set in: (i) almost 2-colorable 3-uniform hypergraphs and, (ii) k-uniform hypergraphs with a blocked-partiteness property–a generalization of the k-partiteness property studied in the work of Bansal and Khot [BK10]. Both the above results were known earlier [GS11, BK10] only assuming the Unique Games Conjecture, and we shall describe the Fourier analytic techniques used to obtain them unconditionally. The talk shall also sketch the applications of the second result which yield tight inapproximability for two well known scheduling problems–Concurrent Open Shop and the Assembly Line Problem.