English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of finding large cliques in random graphs and its "planted"variant, where one wants to recover a clique of size $\omega \gg \log{(n)}$added to an \Erdos-\Renyi graph $G \sim G(n,\frac{1}{2})$, have been intenselystudied. Nevertheless, existing polynomial time algorithms can only recoverplanted cliques of size $\omega = \Omega(\sqrt{n})$. By contrast, informationtheoretically, one can recover planted cliques so long as $\omega \gg\log{(n)}$. In this work, we continue the investigation of algorithms from thesum of squares hierarchy for solving the planted clique problem begun by Meka,Potechin, and Wigderson (MPW, 2015) and Deshpande and Montanari (DM,2015). Ourmain results improve upon both these previous works by showing:  1. Degree four SoS does not recover the planted clique unless $\omega \gg\sqrt n poly \log n$, improving upon the bound $\omega \gg n^{1/3}$ due to DM.A similar result was obtained independently by Raghavendra and Schramm (2015).  2. For $2 < d = o(\sqrt{\log{(n)}})$, degree $2d$ SoS does not recover theplanted clique unless $\omega \gg n^{1/(d + 1)} /(2^d poly \log n)$, improvingupon the bound due to MPW.  Our proof for the second result is based on a fine spectral analysis of thecertificate used in the prior works MPW,DM and Feige and Krauthgamer (2003) bydecomposing it along an appropriately chosen basis. Along the way, we developcombinatorial tools to analyze the spectrum of random matrices with dependententries and to understand the symmetries in the eigenspaces of the setsymmetric matrices inspired by work of Grigoriev (2001).  An argument of Kelner shows that the first result cannot be proved using thesame certificate. Rather, our proof involves constructing and analyzing a newcertificate that yields the nearly tight lower bound by "correcting" thecertificate of previous works.

SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four