Transfer conjecture from Gaussian planted submatrices to planted clique

The Gaussian Planted Submatrix problem has signal parameter β\beta, while the Planted Clique problem is obtained from a centered Erdős–Rényi adjacency matrix with an inserted clique on a random subset of βn\beta\sqrt{n} vertices. Planted clique transfer conjecture. The results of Theorem~ and the Gaussian planted submatrix recovery conjecture hold verbatim when the Gaussian Planted Submatrix problem is replaced by the Planted Clique problem. The paper explains that the discrete structure creates technical challenges and explicitly leaves this transfer as an open problem.

Sources & referencesView supporting material

Primary source

Yuxin Ma and Dmitriy Kunisky, “Nonlinear Laplacians: Tunable principal component analysis under directional prior information”, arXiv:2505.12528 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.