A Simple SVD Algorithm for Finding Hidden Partitions
VAN VU
Source record
Source: Crossref
Published: Oct 9, 2017
DOI: 10.1017/s0963548317000463
Open original source ↗Source abstract
Finding a hidden partition in a random environment is a general and important problem which contains as subproblems many important questions, such as finding a hidden clique, finding a hidden colouring, finding a hidden bipartition, etc . In this paper we provide a simple SVD algorithm for this purpose, addressing a question of McSherry. This algorithm is easy to implement and works for sparse graphs under optimal density assumptions. We also consider an approximating algorithm, which on one hand works under very mild assumptions, but on other hand can sometimes be upgraded to give the exact solution.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.