Michael Kapralov

FOCS Conference 2025 Conference Paper

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs

• Shunhua Jiang
• Michael Kapralov
• Lawrence Li
• Aaron Sidford

In this paper we consider generalized flow problems where there is an m-edge n-node directed graph $G=(V, E)$ and each edge $e \in E$ has a loss factor $\gamma_{e}\gt 0$ governing whether the flow is increased or decreased as it crosses edge e. We provide a randomized $\widetilde{O}\left(\left(m+n^{1. 5}\right) \cdot \operatorname{polylog}\left(\frac{W}{\delta}\right)\right)$ time algorithm for solving the generalized maximum flow and generalized minimum cost flow problems in this setting where $\delta$ is the target accuracy and W is the maximum of all costs, capacities, and loss factors and their inverses. This improves upon the previous state-of-the-art $\widetilde{O}\left(m \sqrt{n} \cdot \log ^{2}\left(\frac{W}{\delta}\right)\right)$ time algorithm, obtained by combining the algorithm of [17] with techniques from [29]. To obtain this result we provide new dynamic data structures and spectral results regarding the matrices associated to generalized flows and apply them through the interior point method framework of [39]. 1. 1 The full version of this paper is available at https: //arxiv. org/abs/2510. 17740.

ICLR Conference 2025 Conference Paper

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions

• Piotr Indyk
• Michael Kapralov
• Kshiteej Sheth
• Tal Wagner

Motivated by the problem of fast processing of attention matrices, we study fast algorithms for computing matrix-vector products for asymmetric Gaussian Kernel matrices $K\in \mathbb{R}^{n\times n}$. $K$'s columns are indexed by a set of $n$ keys $k_1,k_2\ldots, k_n\in \mathbb{R}^d$, rows by a set of $n$ queries $q_1,q_2,\ldots,q_n\in \mathbb{R}^d $, and its $i,j$ entry is $K_{ij} = e^{-\|q_i-k_j\|_2^2/2\sigma^2}$ for some bandwidth parameter $\sigma>0$. Given a vector $x\in \mathbb{R}^n$ and error parameter $\epsilon>0$, our task is to output a $y\in \mathbb{R}^n$ such that $\|Kx-y\|_2\leq \epsilon \|x\|_2$ in time subquadratic in $n$ and linear in $d$. Our algorithms rely on the following modelling assumption about the matrices $K$: the sum of the entries of $K$ scales linearly in $n$, as opposed to worst case quadratic growth. We validate this assumption experimentally, for Gaussian kernel matrices encountered in various settings such as fast attention computation in LLMs. Under this assumption, we obtain the first subquadratic time algorithm for kernel matrix-vector multiplication for unrestricted vectors.

NeurIPS Conference 2025 Conference Paper

Streaming Attention Approximation via Discrepancy Theory

• Ekaterina Kochetkova
• Kshiteej Jitesh Sheth
• Insu Han
• Amir Zandieh
• Michael Kapralov

Large language models (LLMs) have achieved impressive success, but their high memory requirements present challenges for long-context token generation. In this paper we study the streaming complexity of attention approximation, a key computational primitive underlying token generation. Our main contribution is BalanceKV, a streaming algorithm for $\epsilon$-approximating attention computations based on geometric process for selecting a balanced collection of Key and Value tokens as per Banaszczyk's vector balancing theory. We complement our algorithm with space lower bounds for streaming attention computation. Besides strong theoretical guarantees, BalanceKV exhibits empirically validated performance improvements over existing methods, both for attention approximation and end-to-end performance on various long context benchmarks.

SODA Conference 2024 Conference Paper

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations

• Moses Charikar
• Michael Kapralov
• Erik Waingarten

In the kernel density estimation (KDE) problem one is given a kernel K(x, y) and a dataset P of points in a high dimensional Euclidean space, and must prepare a small space data structure that can quickly answer density queries: given a point q, output a (1 + ɛ )-approximation to. The classical approach to KDE (and the more general problem of matrix vector multiplication for kernel matrices) is the celebrated fast multipole method of Greengard and Rokhlin [1983]. The fast multipole method combines a basic space partitioning approach with a multidimensional Taylor expansion, which yields a ≈ log d ( n / ɛ ) query time (exponential in the dimension d ). A recent line of work initiated by Charikar and Siminelakis [2017] achieved polynomial dependence on d via a combination of random sampling and randomized space partitioning, with Backurs et al. [2018] giving an efficient data structure with query time ≈ polylog(1/µ)/ ɛ 2 for smooth kernels. Quadratic dependence on ɛ, inherent to the sampling (i. e. , Monte Carlo) methods above, is prohibitively expensive for small ɛ. This is a classical issue addressed by quasi-Monte Carlo methods in numerical analysis. The high level idea in quasi-Monte Carlo methods is to replace random sampling with a discrepancy based approach - an idea recently applied to coresets for KDE by Phillips and Tai [2020]. The work of Phillips and Tai gives a space efficient data structure with query complexity ≈ 1/( ɛ μ). This is polynomially better in 1/ ɛ, but exponentially worse in 1/μ. In this work we show how to get the best of both worlds: we give a data structure with ≈ polylog(1 /μ)/ ɛ query time for smooth kernel KDE. Our main insight is a new way to combine discrepancy theory with randomized space partitioning inspired by, but significantly more efficient than, that of the fast multipole methods. We hope that our techniques will find further applications to linear algebra for kernel matrices.

NeurIPS Conference 2024 Conference Paper

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models

• Aditya Bhaskara
• Agastya V. Jha
• Michael Kapralov
• Naren S. Manoj
• Davide Mazzali
• Weronika Wrzos-Kaminska

In a graph bisection problem, we are given a graph $G$ with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heuristic, known as spectral clustering, is to output an estimated community assignment based on the eigenvector corresponding to the second-smallest eigenvalue of the Laplacian of $G$. Spectral algorithms can be shown to provably recover the cluster structure for graphs generated from probabilistic models, such as the Stochastic Block Model (SBM). However, spectral clustering is known to be non-robust to model mis-specification. Techniques based on semidefinite programming have been shown to be more robust, but they incur significant computational overheads. In this work, we study the robustness of spectral algorithms against semirandom adversaries. Informally, a semirandom adversary is allowed to ``helpfully'' change the specification of the model in a way that is consistent with the ground-truth solution. Our semirandom adversaries in particular are allowed to add edges inside clusters or increase the probability that an edge appears inside a cluster. Semirandom adversaries are a useful tool to determine the extent to which an algorithm has overfit to statistical assumptions on the input. On the positive side, we identify a wide range of semirandom adversaries under which spectral bisection using the _unnormalized_ Laplacian is strongly consistent, i. e. , it exactly recovers the planted partitioning. On the negative side, we show that in many of these settings, _normalized_ spectral bisection outputs a partitioning that makes a classification mistake on a constant fraction of the vertices. Finally, we demonstrate numerical experiments that complement our theoretical findings.

SODA Conference 2023 Conference Paper

Learning Hierarchical Cluster Structure of Graphs in Sublinear Time

• Michael Kapralov
• Akash Kumar 0009
• Silvio Lattanzi
• Aida Mousavifar

Learning graph cluster structure using few queries is a classical question in property testing, with the fundamental special case, namely expansion testing, considered in the seminal work of Goldreich and Ron[STOC'96]. The most recent results in this line of work design clustering oracles for ( k, ε)-clusterable graphs, which are graphs that can be partitioned into k induced expanders with outer conductance bounded by ε ≪ 1. These oracles, given a graph whose vertex set can be partitioned into a disjoint union of k clusters (i. e. , good expanders) with outer conductances bounded by ε ≪ 1, provide query access to an O (ε log k )- approximation to this ground truth clustering in time ≈ 2 poly( k /ε) n 1/2+ O (ε) per query. Motivated by the rising interest in learning hierarchical structures in large networks, in this paper we introduce ( k, γ)- hierarchically clusterable graphs, a natural hierarchical analog of classical ( k, ε)-clusterable graphs; intuitively, these are graphs that exhibit pronounced hierarchical structure. We give a hierarchical clustering oracle for this model, i. e. a small space data structure that provides query access to a good hierarchical clustering at cost ≈ poly( k ) · n 1/2+ O (γ) per query; notably, the dependence on k is polynomial, in contrast to best known flat clustering oracles. The result relies on several structural properties of hierarchically clusterable graphs that we hope will be of independent interest in sublinear time spectral graph algorithms.

SODA Conference 2023 Conference Paper

Toeplitz Low-Rank Approximation with Sublinear Query Complexity

• Michael Kapralov
• Hannah Lawrence
• Mikhail Makarov
• Cameron Musco
• Kshiteej Sheth

We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix T ∈ ℝ d×d. In particular, for any integer rank k ≤ d and ε, δ > 0, our algorithm makes Õ ( k 2 · log(1/δ) · poly(1/ε)) queries to the entries of T and outputs a rank Õ ( k · log(1/δ)/ε) matrix d×d such that || T – || F ≤ (1 + ε) · || T - T k || F + δ|| Τ || F. Here, || · || F is the Frobenius norm and T k is the optimal rank- k approximation to T, given by projection onto its top k eigenvectors. Õ (·) hides polylog( d ) factors. Our algorithm is structure-preserving, in that the approximation is also Toeplitz. A key technical contribution is a proof that any positive semidefinite Toeplitz matrix in fact has a near-optimal low-rank approximation which is itself Toeplitz. Surprisingly, this basic existence result was not previously known. Building on this result, along with the well-established off-grid Fourier structure of Toeplitz matrices [Cybenko'82], we show that Toeplitz with near optimal error can be recovered with a small number of random queries via a leverage-score-based off-grid sparse Fourier sampling scheme.

SODA Conference 2023 Conference Paper

Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms

• Karl Bringmann
• Michael Kapralov
• Mikhail Makarov
• Vasileios Nakos
• Amir Yagudin
• Amir Zandieh

We are interested in the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier k -sparse domain vector from observing its time domain representation x. In the exact k -sparse case the best known dimension-independent algorithm runs in near cubic time in k and it is unclear whether a faster algorithm like in low dimensions is possible. Beyond that, all known approaches either suffer from an exponential dependence of their runtime on the dimension d or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is O ( N log N ) in any dimension d for N = n d. Our work aims to address the above issues. First, we provide a translation/reduction of the exactly k -sparse Sparse FT problem to a concrete tree exploration task which asks to recover k leaves in a full binary tree under certain exploration rules. Subsequently, we provide (a) an almost quadratic in k time algorithm for the latter task, and (b) evidence that obtaining a strongly subquadratic time for Sparse FT via this approach is likely to be impossible. We achieve the latter by proving a conditional quadratic time lower bound on sparse polynomial multipoint evaluation (the classical non-equispaced sparse Fourier transform problem) which is a core routine in the aforementioned translation. Thus, our results combined can be viewed as an almost complete understanding of this approach, which is the only known approach that yields sublinear time dimension-independent Sparse FT algorithms. Subsequently, we provide a robustification of our algorithm, yielding a robust cubic time algorithm under bounded ℓ 2 noise. This requires proving new structural properties of the recently introduced adaptive aliasing filters combined with a variety of new techniques and ideas. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2. 0.

FOCS Conference 2022 Conference Paper

Factorial Lower Bounds for (Almost) Random Order Streams

• Ashish Chiplunkar
• John Kallaugher
• Michael Kapralov
• Eric Price 0001

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, comprising n/$\ell$ disjoint length-$\ell$ cycles on n vertices, are partitioned randomly among n players. Every edge is annotated with an independent uniformly random bit, and the players’ task is to output, for some cycle in G, the sum (modulo 2) of the bits on its edges, after one round of sequential communication. Our main result is an $\ell^{\Omega(\ell)}$ lower bound on the communication complexity of STREAMINGCYCLES, which is tight up to constant factors in the exponent. Applications of our lower bound for STREAMINGCYCLES include an essentially tight lower bound for component collection in (almost) random order graph streams, making progress towards a conjecture of Peng and Sohler [SODA’18] and the first exponential space lower bounds for random walk generation.

FOCS Conference 2022 Conference Paper

Motif Cut Sparsifiers

• Michael Kapralov
• Mikhail Makarov
• Sandeep Silwal
• Christian Sohler
• 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 clustering, community detection, and analysis of biological and physical networks to name a few (Benson at al. , Tsourakakis at al.). In these applications, the cut structure of motifs plays a crucial role as vertices are partitioned into clusters by cuts whose conductance is based on the number of instances of a particular motif, as opposed to just the number of edges, crossing the cuts. In this paper, we introduce the concept of a motif cut sparsifier. We show that one can compute in polynomial time a sparse weighted subgraph $G^{\prime}$ with only $\widetilde{O}\left(n / \epsilon^{2}\right)$ edges such that for every cut, the weighted number of copies of M crossing the cut in $G^{\prime}$ is within a $1+\epsilon$ factor of the number of copies of M crossing the cut in G, for every constant size motif M. Our work carefully combines the viewpoints of both graph sparsification and hypergraph sparsification. We sample edges which requires us to extend and strengthen the concept of cut sparsifiers introduced in the seminal works of Karger and Benczúr et al. to the motif setting. The task of adapting the importance sampling framework common to efficient graph sparsification algorithms to the motif setting turns out to be nontrivial due to the fact that cut sizes in a random subgraph of G depend non-linearly on the sampled edges. To overcome this, we adopt the viewpoint of hypergraph sparsification to define edge sampling probabilities which are derived from the strong connectivity values of a hypergraph whose hyperedges represent motif instances. Finally, an iterative sparsification primitive inspired by both viewpoints is used to reduce the number of edges in G to nearly linear. In addition, we present a strong lower bound ruling out a similar result for sparsification with respect to induced occurrences of motifs 1. 1 The full version of the paper is found at https: //arxiv. org/abs/2204. 09951

SODA Conference 2022 Conference Paper

Simulating Random Walks in Random Streams

• John Kallaugher
• Michael Kapralov
• Eric Price 0001

NeurIPS Conference 2021 Conference Paper

Efficient and Local Parallel Random Walks

• Michael Kapralov
• Silvio Lattanzi
• Navid Nouri
• Jakab Tardos

Random walks are a fundamental primitive used in many machine learning algorithms with several applications in clustering and semi-supervised learning. Despite their relevance, the first efficient parallel algorithm to compute random walks has been introduced very recently (Łącki et al. ). Unfortunately their method has a fundamental shortcoming: their algorithm is non-local in that it heavily relies on computing random walks out of all nodes in the input graph, even though in many practical applications one is interested in computing random walks only from a small subset of nodes in the graph. In this paper, we present a new algorithm that overcomes this limitation by building random walks efficiently and locally at the same time. We show that our technique is both memory and round efficient, and in particular yields an efficient parallel local clustering algorithm. Finally, we complement our theoretical analysis with experimental results showing that our algorithm is significantly more scalable than previous approaches.

SODA Conference 2021 Conference Paper

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model

• Arnold Filtser
• Michael Kapralov
• Navid Nouri

Graph sketching is a powerful technique introduced by the seminal work of Ahn, Guha and McGregor'12 on connectivity in dynamic graph streams that has enjoyed considerable attention in the literature since then, and has led to near optimal dynamic streaming algorithms for many fundamental problems such as connectivity, cut and spectral sparsifiers and matchings. Interestingly, however, the sketching and dynamic streaming complexity of approximating the shortest path metric of a graph is still far from well-understood. Besides a direct k -pass implementation of classical spanner constructions (recently improved to -passes by Fernandez, Woodruff and Yasuda'20) the state of the art amounts to a O (log k )-pass algorithm of Ahn, Guha and McGregor'12, and a 2-pass algorithm of Kapralov and Woodruff'14. In particular, no single pass algorithm is known, and the optimal tradeoff between the number of passes, stretch and space complexity is open. In this paper we introduce several new graph sketching techniques for approximating the shortest path metric of the input graph. We give the first single pass sketching algorithm for constructing graph spanners: we show how to obtain a Õ ( n ⅔ )-spanner using Õ ( n ) space, and in general a Õ ( n ⅔(1– α ) )-spanner using Õ ( n 1+ α ) space for every α ∊ [0, 1], a tradeoff that we think may be close optimal. We also give new spanner construction algorithms for any number of passes, simultaneously improving upon all prior work on this problem. Finally, we note that unlike the original sketching approach of Ahn, Guha and McGregor'12, none of the existing spanner constructions yield simultaneous communication protocols with low per player information. We give the first such protocols for the spanner problem that use a small number of rounds.

SODA Conference 2021 Conference Paper

Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model

• Michael Kapralov

The bipartite matching problem in the online and streaming settings has received a lot of attention recently. The classical vertex arrival setting, for which the celebrated Karp, Vazirani and Vazirani (KVV) algorithm achieves a 1 – 1/ e approximation, is rather well understood: the 1 – 1/ e approximation is optimal in both the online and semi-streaming setting, where the algorithm is constrained to use n · log O (1) n space. The more challenging the edge arrival model has seen significant progress recently in the online algorithms literature. For the strictly online model (no preemption) approximations better than trivial factor 1/2 have been ruled out [Gamlath et al'FOCS'19]. For the less restrictive online preemptive model a better than -approximation [Epstein et al'STACS'12] and even a better than -approximation[Huang et al'SODA'19] have been ruled out. The recent hardness results for online preemptive matching in the edge arrival model are based on the idea of stringing together multiple copies of a KVV hard instance using edge arrivals. In this paper, we show how to implement such constructions using ideas developed in the literature on Ruzsa-Szemerédi graphs. As a result, we show that any single pass streaming algorithm that approximates the maximum matching in a bipartite graph with n vertices to a factor better than requires n 1+Ω(1/ log log n ) » n log O (1) n space. This gives the first separation between the classical one sided vertex arrival setting and the edge arrival setting in the semi-streaming model.

SODA Conference 2021 Conference Paper

Spectral Clustering Oracles in Sublinear Time

• Grzegorz Gluch
• Michael Kapralov
• Silvio Lattanzi
• Aida Mousavifar
• Christian Sohler

Given a graph G that can be partitioned into k disjoint expanders with outer conductance upper bounded by ∊ « 1, can we efficiently construct a small space data structure that allows quickly classifying vertices of G according to the expander (cluster) they belong to? Formally, we would like an efficient local computation algorithm that misclassifies at most an O (∊) fraction of vertices in every expander. We refer to such a data structure as a spectral clustering oracle. Our main result is a spectral clustering oracle with query time O ∗( n 1/2+ O (∊) ) and preprocessing time that provides misclassification error O (∊ log k ) per cluster for any ∊ « 1/log k. More generally, query time can be reduced at the expense of increasing the preprocessing time appropriately (as long as the product is about n 1+ O (∊) ) – this in particular gives a nearly linear time spectral clustering primitive. The main technical contribution is a sublinear time oracle that provides dot product access to the spectral embedding of G by estimating distributions of short random walks from vertices in G. The distributions themselves provide a poor approximation to the spectral embedding, but we show that an appropriate linear transformation can be used to achieve high precision dot product access. We give an estimator for this linear transformation and analyze it using spectral perturbation bounds and a novel upper bound on the leverage scores of the spectral embedding matrix of a k -clusterable graph. We then show that dot product access to the spectral embedding is sufficient to design a clustering oracle. At a high level our approach amounts to hyperplane partitioning in the spectral embedding of G, but crucially operates on a nested sequence of carefully defined subspaces in the spectral embedding to achieve per cluster recovery guarantees.

FOCS Conference 2021 Conference Paper

Spectral Hypergraph Sparsifiers of Nearly Linear Size

• Michael Kapralov
• Robert Krauthgamer
• Jakab Tardos
• Yuichi Yoshida

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 the sparsifier size are not known, mainly because the hypergraph Laplacian is non-linear, and thus lacks the linear-algebraic structure and tools that have been so effective for graphs. Our main contribution is the first algorithm for constructing $\epsilon$ -spectral sparsifiers for hypergraphs with $O^{\ast}(n)$ hyperedges, where $O^{\ast}$ suppresses $(\epsilon^{-1}\log n)^{O(1)}$ factors. This bound is independent of the rank $r$ (maximum cardinality of a hyperedge), and is essentially best possible due to a recent bit complexity lower bound of $\Omega(nr)$ for hypergraph sparsification. This result is obtained by introducing two new tools. First, we give a new proof of spectral concentration bounds for sparsifiers of graphs; it avoids linear-algebraic methods, replacing e. g. the usual application of the matrix Bernstein inequality and therefore applies to the (non-linear) hypergraph setting. To achieve the result, we design a new sequence of hypergraph-dependent $\epsilon$ -nets on the unit sphere in $\mathbb{R}^{n}$. Second, we extend the weight-assignment technique of Chen, Khanna and Nagda [FOCS'20] to the spectral sparsification setting. Surprisingly, the number of spanning trees after the weight assignment can serve as a potential function guiding the reweighting process in the spectral setting.

STOC Conference 2021 Conference Paper

Towards tight bounds for spectral sparsification of hypergraphs

• Michael Kapralov
• Robert Krauthgamer
• Jakab Tardos
• Yuichi Yoshida

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 applications. However, the current bounds on the size of hypergraph sparsifiers are not as tight as the corresponding bounds for graphs. Our first result is a polynomial-time algorithm that, given a hypergraph on n vertices with maximum hyperedge size r , outputs an є-spectral sparsifier with O * ( nr ) hyperedges, where O * suppresses (є −1 log n ) O (1) factors. This size bound improves the two previous bounds: O * ( n 3 ) [Soma and Yoshida, SODA’19] and O * ( nr 3 ) [Bansal, Svensson and Trevisan, FOCS’19]. Our main technical tool is a new method for proving concentration of the nonlinear analogue of the quadratic form of the Laplacians for hypergraph expanders. We complement this with lower bounds on the bit complexity of any compression scheme that (1+є)-approximates all the cuts in a given hypergraph, and hence also on the bit complexity of every є-cut/spectral sparsifier. These lower bounds are based on Ruzsa-Szemerédi graphs, and a particular instantiation yields an Ω( nr ) lower bound on the bit complexity even for fixed constant є. In the case of hypergraph cut sparsifiers, this is tight up to polylogarithmic factors in n , due to recent result of [Chen, Khanna and Nagda, FOCS’20]. For spectral sparsifiers it narrows the gap to O * ( r ). Finally, for directed hypergraphs, we present an algorithm that computes an є-spectral sparsifier with O * ( n 2 r 3 ) hyperarcs, where r is the maximum size of a hyperarc. For small r , this improves over O * ( n 3 ) known from [Soma and Yoshida, SODA’19], and is getting close to the trivial lower bound of Ω( n 2 ) hyperarcs.

SODA Conference 2020 Conference Paper

Differentially Private Release of Synthetic Graphs

• Marek Eliás 0001
• Michael Kapralov
• Janardhan Kulkarni
• Yin Tat Lee

We propose a ( ϵ, δ )-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. This is the first construction of differentially private cut approximator that allows additive error o ( m ) for all m > n log C n. The best known previous results gave additive O ( n 3/2 ) error and hence only retained information about the cut structure on very dense graphs. Thus, we are making a notable progress on a promiment problem in differential privacy. We also present lower bounds showing that our utility/privacy trade-off is essentially the best possible if one seeks to get purely additive cut approximations.

SODA Conference 2020 Conference Paper

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

• Michael Kapralov
• Aida Mousavifar
• Cameron Musco
• Christopher Musco
• Navid Nouri
• Aaron Sidford
• 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 Õ ( n ) space, and with high probability, recovers a spectral sparsifier from the sketch in Õ ( n ) time. 1 Prior results either achieved near optimal Õ ( n ) space, but Ω( n 2 ) recovery time [Kapralov et al. ‘14], or ran in o ( n 2 ) time, but used polynomially suboptimal space [Ahn et al ‘13]. Our main technical contribution is a novel method for recovering graph edges with high effective resistance from a linear sketch. We show how to do so in nearly linear time by ‘bucketing’ vertices of the input graph into clusters using a coarse approximation to the graph's effective resistance metric. A second main contribution is a new pseudorandom generator (PRG) for linear sketching algorithms. Constructed from a locally computable randomness extractor, our PRG stretches a seed of Õ (n) random bits polynomially in length with just log O (1) n run-time cost per evaluation. This improves on Nisan's commonly used PRG, which in our setting would require Õ ( n ) time per evaluation. Our faster PRG is essential to simultaneously achieving near optimal space and time complexity.

FOCS Conference 2020 Conference Paper

Kernel Density Estimation through Density Constrained Near Neighbor Search

• Moses Charikar
• Michael Kapralov
• Navid Nouri
• Paris Siminelakis

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+ ε)-approximation to μ: =[1/(|P|)]Σ p∈P K(p, q). First, we give a single data structure based on classical near neighbor search techniques that improves upon or essentially matches the query time and space complexity for all radial kernels considered in the literature so far. We then show how to improve both the query complexity and runtime by using recent advances in data-dependent near neighbor search. We achieve our results by giving an new implementation of the natural importance sampling scheme. Unlike previous approaches, our algorithm first samples the dataset uniformly (considering a geometric sequence of sampling rates), and then uses existing approximate near neighbor search techniques on the resulting smaller dataset to retrieve the sampled points that lie at an appropriate distance from the query. We show that the resulting sampled dataset has strong geometric structure, making approximate near neighbor search return the required samples much more efficiently than for worst case datasets of the same size. As an example application, we show that this approach yields a data structure that achieves query time μ -(1+0(1))/4 and space complexity μ -(1+0(1)) for the Gaussian kernel. Our data dependent approach achieves query time μ -0. 173-0(1) and space μ -(1+0(1)) for the Gaussian kernel. The data dependent analysis relies on new techniques for tracking the geometric structure of the input datasets in a recursive hashing process that we hope will be of interest in other applications in near neighbor search.

SODA Conference 2020 Conference Paper

Oblivious Sketching of High-Degree Polynomial Kernels

• Thomas D. Ahle
• Michael Kapralov
• Jakob Bæk Tejs Knudsen
• Rasmus Pagh
• Ameya Velingker
• David P. Woodruff
• 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 scalability: primitives such as kernel PCA or kernel ridge regression generally take prohibitively large quadratic space and (at least) quadratic time, as kernel matrices are usually dense. Some methods for speeding up kernel linear algebra are known, but they all invariably take time exponential in either the dimension of the input point set (e. g. , fast multipole methods suffer from the curse of dimensionality ) or in the degree of the kernel function. Oblivious sketching has emerged as a powerful approach to speeding up numerical linear algebra over the past decade, but our understanding of oblivious sketching solutions for kernel matrices has remained quite limited, suffering from the aforementioned exponential dependence on input parameters. Our main contribution is a general method for applying sketching solutions developed in numerical linear algebra over the past decade to a tensoring of data points without forming the tensoring explicitly. This leads to the first oblivious sketch for the polynomial kernel with a target dimension that is only polynomially dependent on the degree of the kernel function, as well as the first oblivious sketch for the Gaussian kernel on bounded datasets that does not suffer from an exponential dependence on the dimensionality of input data points.

SODA Conference 2020 Conference Paper

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

• Michael 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 small amount of space? We show that this problem cannot be solved using a nontrivially sublinear (in m ) number of samples: m 1− o (1) samples are needed. On the other hand, O (log 2 n ) bits of space suffice to compute an estimate. Our main technical tool is a new peeling type algorithm for matching and its local simulation. We show that a delicate balance between exploration depth and sampling rate allows our simulation to not lose precision over a logarithmic number of levels of recursion and achieve a constant factor approximation. Our algorithm also yields a constant factor approximate local computation algorithm (LCA) for matching with O ( d log n ) exploration starting from any vertex. Previous approaches were based on local simulations of randomized greedy, which take O ( d ) time in expectation over the starting vertex or edge (Yoshida et al’09, Onak et al’12), and could not achieve a better than d 2 run-time. Interestingly, we also show that unlike our algorithm, the local simulation of randomized greedy that is the basis of the most efficient prior results does take ( d 2 ) ≫ O ( d log n ) time for a worst case edge even for.

STOC Conference 2019 Conference Paper

A universal sampling method for reconstructing signals with simple Fourier transforms

• Haim Avron
• Michael Kapralov
• Cameron Musco
• Christopher Musco
• Ameya Velingker
• 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 range, a small number of frequencies, or a few blocks of frequencies -- i.e., bandlimited, sparse, and multiband signals, respectively. More broadly, any prior knowledge on a signal's Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct.

STOC Conference 2019 Conference Paper

An optimal space lower bound for approximating MAX-CUT

• Michael Kapralov
• Dmitry Krachun

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 half of this value as the estimate for the size of the MAX-CUT. On the other extreme, for any fixed є > 0, if one allows Õ( n ) space, a (1+є)-approximate solution to the MAX-CUT value can be obtained by storing an Õ( n )-size sparsifier that essentially preserves MAX-CUT value. Our main result is that any (randomized) single pass streaming algorithm that breaks the 2-approximation barrier requires Ω( n )-space, thus resolving the space complexity of any non-trivial approximations of the MAX-CUT value to within polylogarithmic factors in the single pass streaming model. We achieve the result by presenting a tight analysis of the Implicit Hidden Partition Problem introduced by Kapralov et al. [SODA’17] for an arbitrarily large number of players. In this problem a number of players receive random matchings of Ω( n ) size together with random bits on the edges, and their task is to determine whether the bits correspond to parities of some hidden bipartition, or are just uniformly random. Unlike all previous Fourier analytic communication lower bounds, our analysis does not directly use bounds on the ℓ 2 norm of Fourier coefficients of a typical message at any given weight level that follow from hypercontractivity. Instead, we use the fact that graphs received by players are sparse (matchings) to obtain strong upper bounds on the ℓ 1 norm of the Fourier coefficients of the messages of individual players using their special structure, and then argue, using the convolution theorem, that similar strong bounds on the ℓ 1 norm are essentially preserved (up to an exponential loss in the number of players) once messages of different players are combined. We feel that our main technique is likely of independent interest.

SODA Conference 2019 Conference Paper

Dimension-independent Sparse Fourier Transform

• Michael Kapralov
• Ameya Velingker
• Amir Zandieh

The Discrete Fourier Transform (DFT) is a fundamental computational primitive, and the fastest known algorithm for computing the DFT is the FFT (Fast Fourier Transform) algorithm. One remarkable feature of FFT is the fact that its runtime depends only on the size N of the input vector, but not on the dimensionality of the input domain: FFT runs in time O ( N log N ) irrespective of whether the DFT in question is on ℤ N or ℤ n d for some d > 1, where N = n d. The state of the art for Sparse FFT, i. e. the problem of computing the DFT of a signal that has at most k nonzeros in Fourier domain, is very different: all current techniques for sublinear time computation of Sparse FFT incur an exponential dependence on the dimension d in the runtime. In this paper we give the first algorithm that computes the DFT of a k -sparse signal in time poly( k, log N ) in any dimension d, avoiding the curse of dimensionality inherent in all previously known techniques. Our main tool is a new class of filters that we refer to as adaptive aliasing filters: these filters allow isolating frequencies of a k -Fourier sparse signal using O ( k ) samples in time domain and O ( k log N ) runtime per frequency, in any dimension d. We also investigate natural average case models of the input signal: worst case support in Fourier domain with randomized values and random locations in Fourier domain with worst case signal values. Our techniques lead to an Õ ( k 2 ) time algorithm for the former and an Õ ( k ) time algorithm for the latter.

NeurIPS Conference 2019 Conference Paper

Efficiently Learning Fourier Sparse Set Functions

• Andisheh Amrollahi
• Amir Zandieh
• Michael Kapralov
• 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 set of size $n$ and that are sparse (say $k$-sparse) in the Fourier domain. This is a wide class, that includes graph and hypergraph cut functions, decision trees and more. Our central contribution is the first algorithm that allows learning functions whose Fourier support only contains low degree (say degree $d=o(n)$) polynomials using $O(k d \log n)$ sample complexity and runtime $O( kn \log^2 k \log n \log d)$. This implies that sparse graphs with $k$ edges can, for the first time, be learned from $O(k \log n)$ observations of cut values and in linear time in the number of vertices. Our algorithm can also efficiently learn (sums of) decision trees of small depth. The algorithm exploits techniques from the sparse Fourier transform literature and is easily implementable. Lastly, we also develop an efficient robust version of our algorithm and prove $\ell_2/\ell_2$ approximation guarantees without any statistical assumptions on the noise.

FOCS Conference 2019 Conference Paper

Online Matching with General Arrivals

• Buddhima Gamlath
• Michael Kapralov
• Andreas Maggiori
• Ola Svensson
• 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 randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following. 1) For edge arrivals, randomization does not help - no randomized algorithm is better than 1/2 competitive. 2)For general vertex arrivals, randomization helps - there exists a randomized (1/2+Ω(1)) -competitive online matching algorithm.

FOCS Conference 2018 Conference Paper

Testing Graph Clusterability: Algorithms and Lower Bounds

• Ashish Chiplunkar
• Michael Kapralov
• Sanjeev Khanna
• Aida Mousavifar
• Yuval Peres

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generalization of the well-studied problem of testing graph expansion, where one wants to distinguish between the graph having good expansion (i. e. being a good single cluster) and the graph having a sparse cut (i. e. being a union of at least two clusters). A recent work of Czumaj, Peng, and Sohler (STOC'15) gave an ingenious sublinear time algorithm for testing k-clusterability in time Õ(n^1/2 poly(k)). Their algorithm implicitly embeds a random sample of vertices of the graph into Euclidean space, and then clusters the samples based on estimates of Euclidean distances between the points. This yields a very efficient testing algorithm, but only works if the cluster structure is very strong: it is necessary to assume that the gap between conductances of accepted and rejected graphs is at least logarithmic in the size of the graph G. In this paper we show how one can leverage more refined geometric information, namely angles as opposed to distances, to obtain a sublinear time tester that works even when the gap is a sufficiently large constant. Our tester is based on the singular value decomposition of a natural matrix derived from random walk transition probabilities from a small sample of seed nodes. We complement our algorithm with a matching lower bound on the query complexity of testing clusterability. Our lower bound is based on a novel property testing problem, which we analyze using Fourier analytic tools. As a byproduct of our techniques, we also achieve new lower bounds for the problem of approximating MAX-CUT value in sublinear time.

FOCS Conference 2018 Conference Paper

The Sketching Complexity of Graph and Hypergraph Counting

• John Kallaugher
• Michael Kapralov
• Eric Price 0001

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e. g. , estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been studied extensively in the literature, but many natural settings are still not well understood. In this paper we revisit the subgraph (and hypergraph) counting problem in the sketching model, where the algorithm's state as it processes a stream of updates to the graph is a linear function of the stream. This model has recently received a lot of attention in the literature, and has become a standard model for solving dynamic graph streaming problems. In this paper we give a tight bound on the sketching complexity of counting the number of occurrences of a small subgraph H in a bounded degree graph G presented as a stream of edge updates. Specifically, we show that the space complexity of the problem is governed by the fractional vertex cover number of the graph H. Our subgraph counting algorithm implements a natural vertex sampling approach, with sampling probabilities governed by the vertex cover of H. Our main technical contribution lies in a new set of Fourier analytic tools that we develop to analyze multiplayer communication protocols in the simultaneous communication model, allowing us to prove a tight lower bound. We believe that our techniques are likely to find applications in other settings. Besides giving tight bounds for all graphs H, both our algorithm and lower bounds extend to the hypergraph setting, albeit with some loss in space complexity.

SODA Conference 2017 Conference Paper

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space

• Michael Kapralov
• Sanjeev Khanna
• Madhu Sudan 0001
• Ameya Velingker

We consider the problem of estimating the value of MAXCUT in a graph in the streaming model of computation. We show that there exists a constant ∊ * > 0 such that any randomized streaming algorithm that computes a (1 + ∊ * )- approximation to MAX-CUT requires Ω( n ) space on an n vertex graph. By contrast, there are algorithms that produce a (1 + ∊)-approximation in space O ( n /∊ 2 ) for every ∊ > 0. Our result is the first linear space lower bound for the task of approximating the max cut value and partially answers an open question from the literature [2]. The prior state of the art ruled out (2 - ∊)-approximation in space or (1 + ∊)-approximation in space, for any ∊ > 0. Previous lower bounds for the MAX-CUT problem relied, in essence, on a lower bound on the communication complexity of the following task: Several players are each given some edges of a graph and they wish to determine if the union of these edges is ε-close to forming a bipartite graph, using one-way communication. The previous works proved a lower bound of for this task when ∊ = 1/2, and n 1_ O (∊) for every ∊ > 0, even when one of the players is given a candidate bipartition of the graph and the graph is promised to be bipartite with respect to this partition or ε-far from bipartite. This added information was essential in enabling the previous analyses but also yields a weak bound since, with this extra information, there is an n 1_ O (∊) communication protocol for this problem. In this work, we give an O ( n ) lower bound on the communication complexity of the original problem (without the extra information) for ∊ = Ω(1) in the three-player setting. Obtaining this O ( n ) lower bound on the communication complexity is the main technical result in this paper. We achieve it by a delicate choice of distributions on instances as well as a novel use of the convolution theorem from Fourier analysis combined with graph-theoretic considerations to analyze the communication complexity.

STOC Conference 2017 Conference Paper

An adaptive sublinear-time block sparse fourier transform

• Volkan Cevher
• Michael Kapralov
• Jonathan Scarlett
• Amir Zandieh

The problem of approximately computing the k dominant Fourier coefficients of a vector X quickly, and using few samples in time domain, is known as the Sparse Fourier Transform (sparse FFT) problem. A long line of work on the sparse FFT has resulted in algorithms with O ( k log n log( n / k )) runtime [Hassanieh et al. , STOC'12] and O ( k log n ) sample complexity [Indyk et al. , FOCS'14]. This paper revisits the sparse FFT problem with the added twist that the sparse coefficients approximately obey a ( k 0 , k 1 )-block sparse model. In this model, signal frequencies are clustered in k 0 intervals with width k 1 in Fourier space, and k = k 0 k 1 is the total sparsity.

FOCS Conference 2017 Conference Paper

Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams

• Michael Kapralov
• Jelani Nelson
• Jakub Pachocki
• Zhengyu Wang
• David P. Woodruff
• Mobin Yahyazadeh

In the communication problem UR (universal relation) [25], Alice and Bob respectively receive x, y ∈ {0, 1} n with the promise that x ≠ y. The last player to receive a message must output an index i such that x i ≠ y i. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly Θ(min{n, log(1/δ) log 2 (n/log(1/δ) )}) for failure probability δ. Our lower bound holds even if promised support(y) ⊂ support(x). As a corollary, we obtain optimal lower bounds for ℓ p -sampling in strict turnstile streams for 0 ≤ p n at all points in the stream. We give two different proofs of our main result. The first proof demonstrates that any algorithm A solving sampling problems in turnstile streams in low memory can be used to encode subsets of [n] of certain sizes into a number of bits below the information theoretic minimum. Our encoder makes adaptive queries to A throughout its execution, but done carefully so as to not violate correctness. This is accomplished by injecting random noise into the encoder's interactions with A, which is loosely motivated by techniques in differential privacy. Our correctness analysis involves understanding the ability of A to correctly answer adaptive queries which have positive but bounded mutual information with A's internal randomness, and may be of independent interest in the newly emerging area of adaptive data analysis with a theoretical computer science lens. Our second proof is via a novel randomized reduction from Augmented Indexing [30] which needs to interact with A adaptively. To handle the adaptivity we identify certain likely interaction patterns and union bound over them to guarantee correct interaction on all of them. To guarantee correctness, it is important that the interaction hides some of its randomness from A in the reduction.

ICML Conference 2017 Conference Paper

Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees

• Haim Avron
• Michael Kapralov
• Cameron Musco
• Christopher Musco
• Ameya Velingker
• Amir Zandieh

Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifically, we approach random Fourier features from a spectral matrix approximation point of view, give tight bounds on the number of Fourier features required to achieve a spectral approximation, and show how spectral matrix approximation bounds imply statistical guarantees for kernel ridge regression.

FOCS Conference 2017 Conference Paper

Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average

• Michael Kapralov

The problem of computing the Fourier Transform of a signal whose spectrum is dominated by a small number k of frequencies quickly and using a small number of samples of the signal in time domain (the Sparse FFT problem) has received significant attention recently. It is known how to approximately compute the k-sparse Fourier transform in ≈ k log 2 n time [Hassanieh et al'STOC'12], or using the optimal number O(k log n) of samples [Indyk et al'FOCS'14] in time domain, or come within (log log n) O(1) factors of both these bounds simultaneously, but no algorithm achieving the optimal O(k log n) bound in sublinear time is known. At a high level, sublinear time Sparse FFT algorithms operate by `hashing' the spectrum of the input signal into ≈ k `buckets', identifying frequencies that are `isolated' in their buckets, subtracting them from the signal and repeating until the entire signal is recovered. The notion of `isolation' in a `bucket', inspired by applications of hashing in sparse recovery with arbitrary linear measurements, has been the main tool in the analysis of Fourier hashing schemes in the literature. However, Fourier hashing schemes, which are implemented via filtering, tend to be `noisy' in the sense that a frequency that hashes into a bucket contributes a non-negligible amount to neighboring buckets. This leakage to neighboring buckets makes identification and estimation challenging, and the standard analysis based on isolation becomes difficult to use without losing ω(1) factors in sample complexity. In this paper we propose a new technique for analysing noisy hashing schemes that arise in Sparse FFT, which we refer to as isolation on average. We apply this technique to two problems in Sparse FFT: estimating the values of a list of frequencies using few samples and computing Sparse FFT itself, achieving sample-optimal results in k log O(1) n time for both. We feel that our approach will likely be of interest in designing Fourier sampling schemes for more general settings (e. g. model based Sparse FFT).

ICML Conference 2016 Conference Paper

How to Fake Multiply by a Gaussian Matrix

• Michael Kapralov
• Vamsi K. Potluru
• David P. Woodruff

Have you ever wanted to multiply an n \times d matrix X, with n ≫d, on the left by an m \times n matrix \tilde G of i. i. d. Gaussian random variables, but could not afford to do it because it was too slow? In this work we propose a new randomized m \times n matrix T, for which one can compute T ⋅X in only O(nnz(X)) + \tilde O(m^1. 5 ⋅d^3) time, for which the total variation distance between the distributions T ⋅X and \tilde G ⋅X is as small as desired, i. e. , less than any positive constant. Here nnz(X) denotes the number of non-zero entries of X. Assuming nnz(X) ≫m^1. 5 ⋅d^3, this is a significant savings over the naïve O(nnz(X) m) time to compute \tilde G ⋅X. Moreover, since the total variation distance is small, we can provably use T ⋅X in place of \tilde G ⋅X in any application and have the same guarantees as if we were using \tilde G ⋅X, up to a small positive constant in error probability. We apply this transform to nonnegative matrix factorization (NMF) and support vector machines (SVM).

STOC Conference 2016 Conference Paper

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time

• Michael Kapralov

We consider the problem of computing a k -sparse approximation to the Fourier transform of a length N signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving ℓ 2 /ℓ 2 sparse recovery guarantees using Fourier measurements) using O d ( k log N loglog N ) samples of the signal in time domain and O d ( k log d +3 N ) runtime, where d ≥ 1 is the dimensionality of the Fourier transform. The sample complexity matches the Ω( k log( N / k )) lower bound for non-adaptive algorithms due to [DIPW] for any k ≤ N 1−δ for a constant δ>0 up to an O (loglog N ) factor. Prior to our work a result with comparable sample complexity k log N log O (1) log N and sublinear runtime was known for the Fourier transform on the line [IKP], but for any dimension d ≥ 2 previously known techniques either suffered from a (log N ) factor loss in sample complexity or required Ω( N ) runtime.

SODA Conference 2015 Conference Paper

Streaming Lower Bounds for Approximating MAX-CUT

• Michael Kapralov
• Sanjeev Khanna
• Madhu Sudan 0001

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 half of this value as the estimate for max cut value. On the other extreme, if one allows Õ ( n ) space, then a near-optimal solution to the max cut value can be obtained by storing an Õ ( n )-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor 2). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space. Our main result is that any streaming algorithm that breaks the 2-approximation barrier requires space even if the edges of the input graph are presented in random order Our result is obtained by exhibiting a distribution over graphs which are either bipartite or -far from being bipartite, and establishing that space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that space is also necessary to test if a graph is bipartite or -far from being bipartite. We also show that for any ε > 0, any streaming algorithm that obtains a (1 + ε)-approximation to the max cut value when edges arrive in adversarial order requires n 1 - O (ε) space, implying that Ω( n ) space is necessary to obtain an arbitrarily good approximation to the max cut value.

SODA Conference 2014 Conference Paper

(Nearly) Sample-Optimal Sparse Fourier Transform

• Piotr Indyk
• Michael Kapralov
• Eric Price 0001

SODA Conference 2014 Conference Paper

Approximating matching size from random streams

• Michael Kapralov
• Sanjeev Khanna
• Madhu Sudan 0001

We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. Prior to this work the only approximations known were a folklore approximation with polylogarithmic space in an n vertex graph and a constant approximation with Ω( n ) space. Our work thus gives the first algorithm where both the space and approximation factors are smaller than any polynomial in n. Our algorithm is obtained by effecting a streaming implementation of a simple “local” algorithm that we design for this problem. The local algorithm produces a O ( k · n 1/ k ) approximation to the size of a maximum matching by exploring the radius k neighborhoods of vertices, for any parameter k. We show, somewhat surprisingly, that our local algorithm can be implemented in the streaming setting even for k = Ω (log n /log log n ). Our analysis exposes some of the problems that arise in such conversions of local algorithms into streaming ones, and gives techniques to overcome such problems.

FOCS Conference 2014 Conference Paper

Sample-Optimal Fourier Sampling in Any Constant Dimension

• Piotr Indyk
• Michael Kapralov

We give an algorithm for ℓ 2 /ℓ 2 sparse recovery from Fourier measurements using O(k log N) samples, matching the lower bound of Do Ba-Indyk-Price-Woodruff'10 for non-adaptive algorithms up to constant factors for any k ≤ N 1-δ. The algorithm runs in Õ(N) time. Our algorithm extends to higher dimensions, leading to sample complexity of Õ d (k log N), which is optimal up to constant factors for any d = O(1). These are the first sample optimal algorithms for these problems. A preliminary experimental evaluation indicates that our algorithm has empirical sampling complexity comparable to that of other recovery methods known in the literature, while providing strong provable guarantees on the recovery quality.

FOCS Conference 2014 Conference Paper

Single Pass Spectral Sparsification in Dynamic Streams

• Michael Kapralov
• Yin Tat Lee
• Cameron Musco
• Christopher Musco
• Aaron Sidford

We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions and deletions of edges to a graph, G, our algorithm maintains a randomized linear sketch of the incidence matrix into dimension O(1/∈ 2n polylog(n)). Using this sketch, the algorithm can output a (1±∈) spectral sparsifier for G with high probability. While O(1/∈ 2n polylog(n)) space algorithms are known for computing cut sparsifiers in dynamic streams [1], [2] and spectral sparsifiers in insertion-only streams [3], prior to our work, the best known single pass algorithm for maintaining spectral sparsifiers in dynamic streams required sketches of dimension Ω(1/∈ 2n5/3 ). To achieve our result, we show that, using a coarse sparsifier of G and a linear sketch of G's incidence matrix, it is possible to sample edges by effective resistance, obtaining a spectral sparsifier of arbitrary precision. Sampling from the sketch requires a novel application of ℓ 2 /ℓ 2 sparse recovery, a natural extension of the ℓ 0 methods used for cut sparsifiers in [1]. Recent work of [2] on row sampling for matrix approximation gives a recursive approach for obtaining the required coarse sparsifiers. Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix A T A given a stream of updates to rows in A.

SODA Conference 2013 Conference Paper

Better bounds for matchings in the streaming model

• Michael Kapralov

In this paper we present improved bounds for approximating maximum matchings in bipartite graphs in the streaming model. First, we consider the question of how well maximum matching can be approximated in a single pass over the input when Õ ( n ) space is allowed, where n is the number of vertices in the input graph. Two natural variants of this problem have been considered in the literature: (1) the edge arrival setting, where edges arrive in the stream and (2) the vertex arrival setting, where vertices on one side of the graph arrive in the stream together with all their incident edges. The latter setting has also been studied extensively in the context of online algorithms, where each arriving vertex has to either be matched irrevocably or discarded upon arrival. In the online setting, the celebrated algorithm of Karp-Vazirani-Vazirani achieves a 1 − 1/ e approximation by crucially using randomization (and using Õ ( n ) space). Despite the fact that the streaming model is less restrictive in that the algorithm is not constrained to match vertices irrevocably upon arrival, the best known approximation in the streaming model with vertex arrivals and Õ ( n ) space is the same factor of 1 − 1/ e. We show that no (possibly randomized) single pass streaming algorithm constrained to use Õ ( n ) space can achieve a better than 1 − 1/ e approximation to maximum matching, even in the vertex arrival setting. This leads to the striking conclusion that no single pass streaming algorithm can get any advantage over online algorithms unless it uses significantly more than Õ ( n ) space. Additionally, our bound yields the best known impossibility result for approximating matchings in the edge arrival model (improving upon the bound of 2/3 proved by Goel at al[SODA'12]). Second, we consider the problem of approximating matchings in multiple passes in the vertex arrival setting. We show that a simple fractional load balancing approach achieves approximation ratio in k passes using linear space. Thus, our algorithm achieves the best possible 1 − 1/ e approximation in a single pass and improves upon the approximation in k passes due to Ahn and Guha[ICALP'11]. Additionally, our approach yields an efficient solution to the Gap-Existence problem considered by Charles et al[EC 10].

SODA Conference 2013 Conference Paper

On differentially private low rank approximation

• Michael Kapralov
• Kunal Talwar

SODA Conference 2013 Conference Paper

Online Submodular Welfare Maximization: Greedy is Optimal

• Michael Kapralov
• Ian Post
• Jan Vondrák

We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless NP = RP. Since the Greedy algorithm is known to be 1/2-competitive for monotone submodular valuations, of which coverage is a special case, this proves that Greedy provides the optimal competitive ratio. On the other hand, we prove that Greedy in a stochastic setting with i. i. d. items and valuations satisfying diminishing returns is (1 − 1/ e )-competitive, which is optimal even for coverage valuations, unless NP = RP. For online budget-additive allocation, we prove that no algorithm can be 0. 612-competitive with respect to a natural LP which has been used previously for this problem.

SODA Conference 2012 Conference Paper

On the communication and streaming complexity of maximum bipartite matching

• Ashish Goel
• Michael Kapralov
• Sanjeev Khanna

Consider the following communication problem. Alice holds a graph G A = ( P, Q, E A ) and Bob holds a graph G B = ( P, Q, E B ), where | P | = | Q | = n. Alice is allowed to send Bob a message m that depends only on the graph G A. Bob must then output a matching M ⊆ E A ∪ E B. What is the minimum message size of the message m that Alice sends to Bob that allows Bob to recover a matching of size at least (1 − ∊) times the maximum matching in G A ∪ G B? The minimum message length is the one-round communication complexity of approximating bipartite matching. It is easy to see that the one-round communication complexity also gives a lower bound on the space needed by a one-pass streaming algorithm to compute a (1 − ∊)-approximate bipartite matching. The focus of this work is to understand one-round communication complexity and one-pass streaming complexity of maximum bipartite matching. In particular, how well can one approximate these problems with linear communication and space? Prior to our work, only a ½-approximation was known for both these problems. In order to study these questions, we introduce the concept of an ∊-matching cover of a bipartite graph G, which is a sparse subgraph of the original graph that preserves the size of maximum matching between every subset of vertices to within an additive en error. We give a polynomial time construction of a ½-matching cover of size O ( n ) with some crucial additional properties, thereby showing that Alice and Bob can achieve a ⅔-approximation with a message of size O ( n ). While we do not provide bounds on the size of ∊-matching covers for ∊ < 1/2, we prove that in general, the size of the smallest ∊-matching cover of a graph G on n vertices is essentially equal to the size of the largest so-called ∊-Ruzsa Szemerédi graph on n vertices. We use this connection to show that for any δ > 0, a (⅔ + δ)-approximation requires a communication complexity of n 1+Ω(1/ log log n ). We also consider the natural restrictingon of the problem in which G A and G B are only allowed to share vertices on one side of the bipartition, which is motivated by applications to one-pass streaming with vertex arrivals. We show that a ¾ -approximation can be achieved with a linear size message in this case, and this result is best possible in that super-linear space is needed to achieve any better approximation. Finally, we build on our techniques for the restricted version above to design one-pass streaming algorithm for the case when vertices on one side are known in advance, and the vertices on the other side arrive in a streaming manner together with all their incident edges. This is precisely the setting of the celebrated (1 − 1/ε)-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem [12]. We present here the first deterministic one-pass streaming (1 − 1/ε)-approximation algorithm using O ( n ) space for this setting.

NeurIPS Conference 2011 Conference Paper

Prediction strategies without loss

• Michael Kapralov
• Rina Panigrahy

Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say `predict 0' or `predict 1', and our payoff is $+1$ if the prediction is correct and $-1$ otherwise. We will say that at each point in time the loss of an algorithm is the number of wrong predictions minus the number of right predictions so far. In this paper we are interested in algorithms that have essentially zero (expected) loss over any string at any point in time and yet have small regret with respect to always predicting $0$ or always predicting $1$. For a sequence of length $T$ our algorithm has regret $14\epsilon T $ and loss $2\sqrt{T}e^{-\epsilon^2 T} $ in expectation for all strings. We show that the tradeoff between loss and regret is optimal up to constant factors. Our techniques extend to the general setting of $N$ experts, where the related problem of trading off regret to the best expert for regret to the 'special' expert has been studied by Even-Dar et al. (COLT'07). We obtain essentially zero loss with respect to the special expert and optimal loss/regret tradeoff, improving upon the results of Even-Dar et al (COLT'07) and settling the main question left open in their paper. The strong loss bounds of the algorithm have some surprising consequences. First, we obtain a parameter free algorithm for the experts problem that has optimal regret bounds with respect to $k$-shifting optima, i. e. bounds with respect to the optimum that is allowed to change arms multiple times. Moreover, for {\em any window of size $n$} the regret of our algorithm to any expert never exceeds $O(\sqrt{n(\log N+\log T)})$, where $N$ is the number of experts and $T$ is the time horizon, while maintaining the essentially zero loss property.

STOC Conference 2010 Conference Paper

Perfect matchings in o( n log n ) time in regular bipartite graphs

• Ashish Goel
• Michael Kapralov
• Sanjeev Khanna

In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m√n). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the O(m) time bound was improved first to ~ O(min m, n 2.5 /d) and then to ~O(min {m, n 2 /d\}). In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated alternating random walk to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time O(n log 2 n), with O(m) pre-processing time; this gives a simple O(m+mn log 2 n) time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix. We show that randomization is crucial for obtaining o(nd) time algorithms by establishing an Ω(nd) lower bound for deterministic algorithms. We also show that there does not exist a randomized algorithm that finds a matching in a regular bipartite multigraph and takes o(n log n) time with high probability.

NeurIPS Conference 2009 Conference Paper

Factor Modeling for Advertisement Targeting

• Ye Chen
• Michael Kapralov
• John Canny
• Dmitry Pavlov

We adapt a probabilistic latent variable model, namely GaP (Gamma-Poisson), to ad targeting in the contexts of sponsored search (SS) and behaviorally targeted (BT) display advertising. We also approach the important problem of ad positional bias by formulating a one-latent-dimension GaP factorization. Learning from click-through data is intrinsically large scale, even more so for ads. We scale up the algorithm to terabytes of real-world SS and BT data that contains hundreds of millions of users and hundreds of thousands of features, by leveraging the scalability characteristics of the algorithm and the inherent structure of the problem including data sparsity and locality. Specifically, we demonstrate two somewhat orthogonal philosophies of scaling algorithms to large-scale problems, through the SS and BT implementations, respectively. Finally, we report the experimental results using Yahoos vast datasets, and show that our approach substantially outperform the state-of-the-art methods in prediction accuracy. For BT in particular, the ROC area achieved by GaP is exceeding 0. 95, while one prior approach using Poisson regression yielded 0. 83. For computational performance, we compare a single-node sparse implementation with a parallel implementation using Hadoop MapReduce, the results are counterintuitive yet quite interesting. We therefore provide insights into the underlying principles of large-scale learning.

SODA Conference 2009 Conference Paper

Perfect matchings via uniform sampling in regular bipartite graphs

• Ashish Goel
• Michael Kapralov
• Sanjeev Khanna