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

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

Type: Preprint

Publication Date: 2016-01-01

Citations: 1

DOI: https://doi.org/10.48550/arxiv.1604.03084

View Publication

Locations

arXiv (Cornell University) - View - PDF
DSpace@MIT (Massachusetts Institute of Technology) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+ PDF Chat	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2019	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+ PDF Chat	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin
+	Sum-of-Squares Lower Bounds for Sparse Independent Set	2021	Chris Jones Aaron Potechin Goutham Rajendran Madhur Tulsiani Jeff Xu
+	Sum-of-squares lower bounds for planted clique	2015	Raghu Meka Aaron Potechin Avi Wigderson
+	Sum-of-squares lower bounds for planted clique	2015	Raghu Meka Aaron Potechin Avi Wigderson
+ PDF Chat	Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs	2024	Pravesh K. Kothari Aaron Potechin Jeff Xu
+	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems	2015	Yash Deshpande Andrea Montanari
+	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems	2015	Yash Deshpande Andrea Montanari
+	Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs	2024	Pravesh K. Kothari Aaron Potechin Jeff Xu
+	Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection	2015	Andrea Montanari Subhabrata Sen
+	On the integrality gap of degree-4 sum of squares for planted clique	2016	Samuel B. Hopkins Pravesh K. Kothari Aaron Potechin Prasad Raghavendra Tselil Schramm
+ PDF Chat	Sum-of-squares Lower Bounds for Planted Clique	2015	Raghu Meka Aaron Potechin Avi Wigderson
+ PDF Chat	Semirandom Planted Clique and the Restricted Isometry Property	2024	Jarosław Błasiok Rares-Darius Buhai Pravesh K. Kothari David Steurer
+	Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique	2013	Raghu Meka Avi Wigderson
+	The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings	2023	Jiaxin Hou Yong Sheng Soh Antonios Varvitsiotis
+	How Well Do Local Algorithms Solve Semidefinite Programs?	2016	Fan Zhou Andrea Montanari
+	Semidefinite programs on sparse random graphs and their application to community detection	2016	Andrea Montanari Subhabrata Sen
+ PDF Chat	Sum-of-Squares Lower Bounds for Sparse Independent Set	2022	Chris Jones Aaron Potechin Goutham Rajendran Madhur Tulsiani Jeff Xu

Works That Cite This (1)

Action	Title	Year	Authors
+	Algorithms Approaching the Threshold for Semi-random Planted Clique	2023	Rares-Darius Buhai Pravesh K. Kothari David Steurer

Works Cited by This (0)

Action	Title	Year	Authors