Random Instances of a Graph Coloring Problem Are Hard

Ramarathnam Venkatesan, Leonid A. Levin

Browse the full STOC paper archive.