1 Search Results for "Pang, Shuo"

Document

DOI: 10.4230/LIPIcs.CCC.2021.26

SOS Lower Bound for Exact Planted Clique

Authors: Shuo Pang

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

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.

Cite as

Shuo Pang. SOS Lower Bound for Exact Planted Clique. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 26:1-26:63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.26},
  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}
}

Refine by Author
1 Pang, Shuo

Refine by Classification
1 Mathematics of computing → Random graphs
1 Theory of computation → Proof complexity
1 Theory of computation → Semidefinite programming

Refine by Keyword
1 Sum-of-Squares
1 average-case lower bound
1 planted clique
1 random graphs

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Pang, Shuo"

SOS Lower Bound for Exact Planted Clique

Abstract

Cite as

Thanks for your feedback!

Could not send message