A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| 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 |
| _version_ | 1826199933247553536 |
|---|---|
| author | Barak, Boaz Hopkins, Samuel B. Kothari, Pravesh Potechin, Aaron Moitra, Ankur Kelner, Jonathan Adam |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Barak, Boaz Hopkins, Samuel B. Kothari, Pravesh Potechin, Aaron Moitra, Ankur Kelner, Jonathan Adam |
| author_sort | Barak, Boaz |
| collection | MIT |
| description | 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 constant c > 0. This yields a nearly tight n[superscript 1/2-o(1))] bound on the value of this program for any degree d = o(log n). Moreover we introduce a new framework that we call pseudo-calibration to construct Sum-of-Squares lower bounds. This framework is inspired by taking a computational analogue of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others. |
| first_indexed | 2024-09-23T11:28:07Z |
| format | Article |
| id | mit-1721.1/116092 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:28:07Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1160922022-09-27T19:46:09Z A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem Barak, Boaz Hopkins, Samuel B. Kothari, Pravesh Potechin, Aaron Moitra, Ankur Kelner, Jonathan Adam Massachusetts Institute of Technology. Department of Mathematics Moitra, Ankur Kelner, Jonathan Adam 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 constant c > 0. This yields a nearly tight n[superscript 1/2-o(1))] bound on the value of this program for any degree d = o(log n). Moreover we introduce a new framework that we call pseudo-calibration to construct Sum-of-Squares lower bounds. This framework is inspired by taking a computational analogue of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others. 2018-06-05T15:05:11Z 2018-06-05T15:05:11Z 2016-12 2016-10 2018-05-24T13:26:20Z Article http://purl.org/eprint/type/ConferencePaper 978-1-5090-3933-3 http://hdl.handle.net/1721.1/116092 Barak, Boaz, et al. "A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem." 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 9-11 October, 2016, New Brunswick, New Jersey, IEEE, 2016 © 2016 IEEE https://orcid.org/0000-0001-7047-0495 https://orcid.org/0000-0002-4257-4198 http://dx.doi.org/10.1109/FOCS.2016.53 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Barak, Boaz Hopkins, Samuel B. Kothari, Pravesh Potechin, Aaron Moitra, Ankur Kelner, Jonathan Adam A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem |
| title | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem |
| title_full | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem |
| title_fullStr | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem |
| title_full_unstemmed | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem |
| title_short | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem |
| title_sort | nearly tight sum of squares lower bound for the planted clique problem |
| url | http://hdl.handle.net/1721.1/116092 https://orcid.org/0000-0001-7047-0495 https://orcid.org/0000-0002-4257-4198 |
| work_keys_str_mv | AT barakboaz anearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT hopkinssamuelb anearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT kotharipravesh anearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT potechinaaron anearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT moitraankur anearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT kelnerjonathanadam anearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT barakboaz nearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT hopkinssamuelb nearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT kotharipravesh nearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT potechinaaron nearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT moitraankur nearlytightsumofsquareslowerboundfortheplantedcliqueproblem AT kelnerjonathanadam nearlytightsumofsquareslowerboundfortheplantedcliqueproblem |