License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2021.26
URN: urn:nbn:de:0030-drops-143000
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14300/
Pang, Shuo
SOS Lower Bound for Exact Planted Clique
Abstract
We prove a SOS degree lower bound for the planted clique problem on the Erdös-Rényi random graph G(n,1/2). The bound we get is degree d = Ω(ε²log n/log log n) for clique size ω = n^{1/2-ε}, which is almost tight. This improves the result of [Barak et al., 2019] for the "soft" version of the problem, where the family of the equality-axioms generated by x₁+...+x_n = ω is relaxed to one inequality x₁+...+x_n ≥ ω.
As a technical by-product, we also "naturalize" certain techniques that were developed and used for the relaxed problem. This includes a new way to define the pseudo-expectation, and a more robust method to solve out the coarse diagonalization of the moment matrix.
BibTeX - Entry
@InProceedings{pang:LIPIcs.CCC.2021.26,
author = {Pang, Shuo},
title = {{SOS Lower Bound for Exact Planted Clique}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {26:1--26:63},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-193-1},
ISSN = {1868-8969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14300},
URN = {urn:nbn:de:0030-drops-143000},
doi = {10.4230/LIPIcs.CCC.2021.26},
annote = {Keywords: Sum-of-Squares, planted clique, random graphs, average-case lower bound}
}
|
Keywords: |
|
Sum-of-Squares, planted clique, random graphs, average-case lower bound |
|
Collection: |
|
36th Computational Complexity Conference (CCC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
08.07.2021 |
