5 papers · 1 filter
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 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…
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…