Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Home

Person

Mikhail Makarov

This person has left EPFL

About
Privacy
Disclaimer

Graph Chatbot

Related publications (4)

Page 1 of 1

Graph sparsification, sketching and adaptivity

Mikhail Makarov

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

Motif Cut Sparsifiers

Mikhail Kapralov, Jakab Tardos, Mikhail Makarov

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

On the Streaming Complexity of Expander Decomposition

Davide Mazzali, Mikhail Kapralov, Yu Chen, Mikhail Makarov

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