Semirandom Planted Clique via 1-norm Isometry Property

Venkatesan Guruswami, Hsin-Po Wang

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.…