Semirandom Planted Clique via 1-norm Isometry Property
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911018779672576 |
|---|---|
| author | Guruswami, Venkatesan Wang, Hsin-Po |
| author_facet | Guruswami, Venkatesan Wang, Hsin-Po |
| contents | We give a polynomial-time algorithm that finds a planted clique of size $k \ge \sqrt{n \log n}$ in the semirandom model, improving the state-of-the-art $\sqrt{n} (\log n)^2$ bound. This $\textit{semirandom planted clique problem}$ concerns finding the planted subset $S$ of $k$ vertices of a graph $G$ on $V$, where the induced subgraph $G[S]$ is complete, the cut edges in $G[S; V \setminus S]$ are random, and the remaining edges in $G[V \setminus S]$ are adversarial.
An elegant greedy algorithm by Blasiok, Buhai, Kothari, and Steurer [BBK24] finds $S$ by sampling inner products of the columns of the adjacency matrix of $G$, and checking if they deviate significantly from typical inner products of random vectors. Their analysis uses a suitably random matrix that, with high probability, satisfies a certain restricted isometry property. Inspired by Wootters's work on list decoding, we put forth and implement the $1$-norm analog of this argument, and quantitatively improve their analysis to work all the way up to the conjectured optimal $\sqrt{n \log n}$ bound on clique size, answering one of the main open questions posed in [BBK24]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17916 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Semirandom Planted Clique via 1-norm Isometry Property Guruswami, Venkatesan Wang, Hsin-Po Data Structures and Algorithms Probability We give a polynomial-time algorithm that finds a planted clique of size $k \ge \sqrt{n \log n}$ in the semirandom model, improving the state-of-the-art $\sqrt{n} (\log n)^2$ bound. This $\textit{semirandom planted clique problem}$ concerns finding the planted subset $S$ of $k$ vertices of a graph $G$ on $V$, where the induced subgraph $G[S]$ is complete, the cut edges in $G[S; V \setminus S]$ are random, and the remaining edges in $G[V \setminus S]$ are adversarial. An elegant greedy algorithm by Blasiok, Buhai, Kothari, and Steurer [BBK24] finds $S$ by sampling inner products of the columns of the adjacency matrix of $G$, and checking if they deviate significantly from typical inner products of random vectors. Their analysis uses a suitably random matrix that, with high probability, satisfies a certain restricted isometry property. Inspired by Wootters's work on list decoding, we put forth and implement the $1$-norm analog of this argument, and quantitatively improve their analysis to work all the way up to the conjectured optimal $\sqrt{n \log n}$ bound on clique size, answering one of the main open questions posed in [BBK24]. |
| title | Semirandom Planted Clique via 1-norm Isometry Property |
| topic | Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2506.17916 |