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

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

Show other versions (1)

We prove that with high probability over the choice of a random graph G from the Erds-Rényi distribution G(n,1/2), the n[superscript o(d)]-time degree d Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least n[superscript 1/2-c(d/log n)1/2] for some c...

Full description

Bibliographic Details
Main Authors: Barak, Boaz, Hopkins, Samuel B., Kothari, Pravesh, Potechin, Aaron, Moitra, Ankur, Kelner, Jonathan Adam
Other Authors: Massachusetts Institute of Technology. Department of Mathematics
Format: Article
Published: Institute of Electrical and Electronics Engineers (IEEE) 2018
Online Access:http://hdl.handle.net/1721.1/116092
https://orcid.org/0000-0001-7047-0495
https://orcid.org/0000-0002-4257-4198

Similar Items

Similar Items