A Simple SVD Algorithm for Finding Hidden Partitions

Content Provider	Scilit
Author	Vu, Van
Copyright Year	2017
Description	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.
Related Links	http://arxiv.org/pdf/1404.3918 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/3691FFE262617493CEC469769154EA19/S0963548317000463a.pdf/div-class-title-a-simple-svd-algorithm-for-finding-hidden-partitions-div.pdf
Ending Page	140
Page Count	17
Starting Page	124
ISSN	09635483
e-ISSN	14692163
DOI	10.1017/s0963548317000463
Journal	Combinatorics, Probability and Computing
Issue Number	1
Volume Number	27
Language	English
Publisher	Cambridge University Press (CUP)
Publisher Date	2017-10-09
Access Restriction	Open
Subject Keyword	Combinatorics, Probability and Computing Primary 68q87 Secondary 68w20
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics