658 citations · 1.9k across the 78 of their papers we have counts for
7 papers · 1 filter
A Proof Of The Block Model Threshold Conjecture
Elchanan Mossel, Joe Neeman, Allan Sly
We study a random graph model named the "block model" in statistics and the "planted partition model" in theoretical computer science. In its simplest form, this is a random graph…
Maximum independent sets on random regular graphs
Jian Ding, Allan Sly, Nike Sun
We determine the asymptotics of the independence number of the random -regular graph for all . It is highly concentrated, with constant-order fluctuations around $nα_…
Satisfiability threshold for random regular NAE-SAT
Jian Ding, Allan Sly, Nike Sun
We consider the random regular -NAE-SAT problem with variables each appearing in exactly clauses. For all exceeding an absolute constant , we establish explicit…
Belief propagation, robust reconstruction and optimal recovery of block models
Elchanan Mossel, Joe Neeman, Allan Sly
We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities and for inter- and intra-block edge probabilities,…
Spectral redemption: clustering sparse networks
Florent Krzakala, Cristopher Moore, Elchanan Mossel +4
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal,…
Distances in critical long range percolation
Jian Ding, Allan Sly
We study the long range percolation model on where sites and are connected with probability . Graph distances are now well understood for all expo…