5 papers
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…
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…
Spectral Clustering with Side Information
Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova +3
In the graph clustering problem with a planted solution, the input is a graph on vertices partitioned into clusters, and the task is to infer the clusters from graph struct…
On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
Aditya Bhaskara, Agastya Vibhuti Jha, Michael Kapralov +3
In a graph bisection problem, we are given a graph with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heurist…
A simpler winning strategy for Sim
Weronika Wrzos-Kaminska
We give a simple human-playable winning strategy for the second player in the game of Sim.