A nearly tight Sum-of-Squares lower bound for the Planted Clique problem

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

Abstract

Publication
Manuscript
Date
May, 2016
Links
PDF