Publications de Mikhail Makarov

Graph sparsification, sketching and adaptivity

Many challenges of modern graph processing stem from the fact that graphs have become massive and change frequently. Numerous techniques have been developed to address those issues, with graph cut sparsification offering to replace original graphs with th ...

EPFL2025

On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space

Mikhail Kapralov, Mikhail Makarov

Locality-sensitive hashing (Indyk-Motwani'98) is a classical data structure for approximate nearest neighbor search. It allows, after a close to linear time preprocessing of the input dataset, to find an approximately nearest neighbor of any fixed query in ...

Association for Computing Machinery (ACM)2025

On the Streaming Complexity of Expander Decomposition

Mikhail Kapralov, Mikhail Makarov, Yu Chen

In this paper we study the problem of finding (ϵ, ϕ)-expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions. The goal is to partition the vertex set so that every component induces a ϕ- ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

Motif Cut Sparsifiers

Mikhail Kapralov, Mikhail Makarov, Jakab Tardos

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022