Sum-of-squares lower bounds for densest \(k\)-subgraph

DOI10.1145/3564246.3585221MaRDI QIDQ6499217

Aaron Potechin, Goutham Rajendran, Jeff Xu, Chris V. Jones

Publication date: 8 May 2024

zbMATH Keywords

average-case complexitydensest \(k\)-subgraphsum-of-squares lower bounds

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Sum-of-squares lower bounds for densest \(k\)-subgraph