6 papers
Recovering Planted Colorings in Sublinear Time
Weronika Wrzos-Kaminska
We give a sublinear algorithm for the planted -coloring problem. Given an expander with a planted coloring, the goal is to efficiently determine the color class of a given v…
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 condu…
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…
Weighted Matching in the Random-Order Streaming and Robust Communication Models
Diba Hashemi, Weronika Wrzos-Kaminska
We study the maximum weight matching problem in the random-order semi-streaming model and in the robust communication model. Unlike many other sublinear models, in these two framew…