Hardness of Finding Independent Sets in Almost 3-Colorable Graphs.

Irit Dinur, Subhash Khot, Will Perkins, Muli Safra

Browse the full FOCS paper archive.