Person

Mikhail Kapralov

Related publications (23)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds

Testing graph cluster structure has been a central object of study in property testing since the foundational work of Goldreich and Ron [STOC’96] on expansion testing, i.e. the problem of distinguishing between a single cluster (an expander) and a graph th ...

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

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

Streaming Algorithms for Connectivity Augmentation

Mikhail Kapralov

We study the k-connectivity augmentation problem (k-CAP) in the single-pass streaming model. Given a (k − 1)-edge connected graph G = (V, E) that is stored in memory, and a stream of weighted edges (also called links) L with weights in {0, 1, . . ., W }, t ...

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

On the Streaming Complexity of Expander Decomposition

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

Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems

Mikhail Kapralov

Graphs processing has become an important part of various areas of computing, including machine learning, medical applications, social network analysis, computational sciences, and others. A growing amount of the associated graph processing workloads are d ...

2023

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

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...

IEEE COMPUTER SOC2022

Factorial Lower Bounds for (Almost) Random Order Streams

Mikhail Kapralov

In this paper we introduce and study the STREAMINGCYCLES problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental in streaming lower bounds over the past decade. In this problem the edges of a graph G ...

IEEE COMPUTER SOC2022

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Mikhail Kapralov, Jakab Tardos

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...

ASSOC COMPUTING MACHINERY2021

Kernel Density Estimation through Density Constrained Near Neighbor Search

Mikhail Kapralov, Navid Nouri

In this paper we revisit the kernel density estimation problem: given a kernel K(x, y) and a dataset of n points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query q, a (1 + epsilon)-approximation to mu := ...

IEEE2020

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Mikhail Kapralov, Amir Zandieh, Navid Nouri

Random binning features, introduced in the seminal paper of Rahimi and Recht '07, are an efficient method for approximating a kernel matrix using locality sensitive hashing. Random binning features provide a very simple and efficient way to approximate the ...

ADDISON-WESLEY PUBL CO2020

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Oblivious Sketching of High-Degree Polynomial Kernels

Mikhail Kapralov, Amir Zandieh

Kernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimensional spaces. A major disadvantage of kernel methods is their poor scalabili ...

ASSOC COMPUTING MACHINERY2020

Differentially Private Release of Synthetic Graphs

Mikhail Kapralov, Marek Elias

We propose a (epsilon, delta)-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G' approximating all cuts of the input graph up to an additive error of O (root mn/epsil ...

ASSOC COMPUTING MACHINERY2020

Efficiently Learning Fourier Sparse Set Functions

Mikhail Kapralov, Amir Zandieh, Andreas Krause

Learning set functions is a key challenge arising in many domains, ranging from sketching graphs to black-box optimization with discrete parameters. In this paper we consider the problem of efficiently learning set functions that are defined over a ground ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019

Online Matching with General Arrivals

Mikhail Kapralov, Ola Nils Anders Svensson, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomi ...

IEEE COMPUTER SOC2019

Perfect Matchings in O (n(1.5)) Time in Regular Bipartite Graphs

Ashish Goel, Mikhail Kapralov

2019

An Optimal Space Lower Bound for Approximating MAX-CUT

Mikhail Kapralov

We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output hal ...

ASSOC COMPUTING MACHINERY2019

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Mikhail Kapralov, Amir Zandieh

Reconstructing continuous signals based on a small number of discrete samples is a fundamental problem across science and engineering. We are often interested in signals with "simple" Fourier structure - e.g., those involving frequencies within a bounded r ...

ASSOC COMPUTING MACHINERY2019