Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon.

Jonas Holmerin

Browse the full STOC paper archive.