Fall 2013

Hardness of Maximum Independent Set in Structured Hypergraphs

Monday, Aug. 26, 2013 11:30 am11:55 am

Add to Calendar

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.