No SDP Needed for Efficiently Recovering Planted Regular Bipartite Graphs

We study exact recovery of an arbitrary (adversarial) \(d\)-regular bipartite subgraph \(S\) of size \(k\)planted in a random Erdős-Rényi \(G(n,\ p)\) graph. Prior algorithms by Kumar, Louis, and Paul [ICALP 2022], and Louis, Paul, and Raghavendra [COLT 2025] either solve a costly semidefinite program (SDP), or perform subspace enumeration that has a runtime exponential in a parameter \(\ell \approx k/d)\). We show that nothing exotic is needed: and our simple Eigenspace Thresholding algorithm which, (i) computes the bottom few (\(\ell \approx k/d)\)) many eigenvectors of the adjacency matrix, (ii) thresholds their coordinates at absolute value \(c/\sqrt {\ell k})\) (for small constant \(c\)) and accumulates the selected vertices, and (iii) uses a standard matching-based clean-up step to fully recover the planted graph.