A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.

Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

Browse the full FOCS paper archive.