Personne
Mikhail Kapralov
Publications associées (16)
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 SOC2022Motif 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 SOC2022Towards 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 MACHINERY2021Fast and Space Efficient Spectral Sparsification in Dynamic Streams
Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar
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 MACHINERY2020Oblivious 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 MACHINERY2020Kernel Density Estimation through Density Constrained Near Neighbor Search
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 := ...
IEEE2020Differentially Private Release of Synthetic Graphs
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 MACHINERY2020Space 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 MACHINERY2020Scaling 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 CO2020A 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