1 Search Results for "Pang, Shuo"

SOS Lower Bound for Exact Planted Clique

Authors: Shuo Pang

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

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

  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/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

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail