5 papers
Provable Quantization with Randomized Hadamard Transform
Ying Feng, Piotr Indyk, Michael Kapralov +2
Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federa…
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…