Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Recovering Communities in Structured Random Graphs
Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska
The problem of recovering planted community structure in random graphs has received a lot of attention in the literature on the stochastic block model, where the input is a random…
cs.DS2026
Spectral Clustering in Birthday Paradox Time
Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska
Given a vertex in a -clusterable graph, i.e. a graph whose vertex set can be partitioned into a disjoint union of -expanders of size with outer conducta…