Spectral recovery of a planted triangle-dense subgraph

Sam van der Poel, Cheng Mao, Benjamin McKenna

Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computa…