Semirandom Planted Clique via 1-norm Isometry Property

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 $\mathit{\text{semirandom}}\mathit{\text{planted}}\mathit{\text{clique}}\mathit{\text{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].