Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs.

Pravesh K. Kothari, Aaron Potechin, Jeff Xu

Browse the full STOC paper archive.