Michael Kapralov

E-mail: lastname at mit dot edu

I am a postdoc at the Theory of Computation Group at MIT CSAIL.

I recently completed my PhD at Stanford iCME, where I was advised by Ashish Goel.

Research interests: I am interested in theoretical computer science, in particular algorithm design. I enjoy working on classical combinatorial optimization problems as well as problems motivated by modern data models, such as online and streaming algorithms and differential privacy.

Recent papers:

Better bounds for matchings in the streaming model, SODA 2013
M. Kapralov
[Abstract]
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 $\tilde O(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 $\tilde O(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 $\tilde O(n)$ space is the same factor of $1-1/e$.
Our main result in this paper shows that no (possibly randomized) single pass streaming algorithm constrained to use $\tilde O(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 $\tilde O(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]).
We also 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 $1-e^{-k}k^{k-1}/(k-1)!=1-\frac1{\sqrt{2\pi k}}+o(1/k)$ 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 $1-O(\sqrt{\log\log k/k})$ 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].

On differentially private low rank approximation, SODA 2013
M. Kapralov and K. Talwar
[Abstract]
Low rank approximation is a fundamental computational primitive widely used in data analysis. In many applications the dataset that the algorithm operates on may contain sensitive information about contributing individuals (e.g. user/movie ratings in the Netflix challenge), motivating the need to design low rank approximation algorithms that preserve privacy of individual entries of the input matrix.
In this paper, we give a polynomial time algorithm that, given a privacy parameter $\epsilon>0$, for a symmetric matrix $A$, outputs an $\epsilon$-differentially approximation to the principal eigenvector of $A$, and then show how this algorithm can be used to obtain a differentially private rank-$k$ approximation. We also provide lower bounds showing that our utility/privacy tradeoff is close to best possible.
While there has been significant progress on this problem recently for a weaker notion of privacy, namely $(\epsilon, \delta)$-differential privacy [HR12, BBDS12], our result is the first to achieve $(\epsilon, 0)$-differential privacy guarantees with a near-optimal utility/privacy tradeoff in polynomial time.

Online submodular welfare maximization: greedy is optimal, SODA 2013
M. Kapralov, I. Post and J. Vondrak
[Abstract]
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.

Embedding paths into trees: VM placement to minimize congestion, ESA 2012
D. Dutta, M. Kapralov, I. Post, R. Shinde
[Abstract]
Modern cloud infrastructure providers allow customers to rent compute capability in the form of a network of virtual machines (VMs) with bandwidth guarantees between pairs of VMs. Typical requests are in the form of a chain of VMs with an uplink bandwidth to the gateway node of the network (rooted path requests), and most data center architectures route network packets along a spanning tree of the physical network. VMs are instantiated inside servers which reside at the leaves of this network, leading to the following optimization problem: given a rooted tree network $T$ and a set of rooted path requests, find an embedding of the requests that minimize link congestion.
Our main result is an algorithm that given a rooted tree network $T$ with $n$ leaves and set of weighted rooted path requests, embeds a $1-\epsilon$ fraction of the requests with congestion at most $poly(\log{n}, \log \theta ,\epsilon^{-1})\cdot\text{OPT}$ (approximation is necessary since the problem is NP-hard). Here $\text{OPT}$ is the congestion of the optimal embedding and $\theta$ is the ratio of the maximum to minimum weights of the path requests. We also obtain a $O(H\log n/\epsilon^2)$ approximation if node capacities can be augmented by a $1+\epsilon$ factor (here $H$ is the height of the tree). Our algorithm applies a randomized rounding scheme based on Group Steiner Tree rounding to a novel LP relaxation of the set of subtrees of $T$ with a given number of leaves that may be of independent interest.

NNS lower bounds via metric expansion for $l_\infty$ and EMD, ICALP 2012
M. Kapralov and R. Panigrahy
[Abstract]
We give new lower bounds for randomized NNS data structures in the cell probe model based on robust metric expansion for two metric spaces: $l_\infty$ and Earth Mover Distance (EMD) in high dimensions. In particular, our results imply stronger non-embedability for these metric spaces into $l_1$. The main components of our approach are a strengthening of the isoperimetric inequality for the distribution on $l_\infty$ introduced by Andoni et al [FOCS'08] and a robust isoperimetric inequality for EMD on quotients of the boolean hypercube.

Spectral sparsification via random spanners, ITCS 2012
M. Kapralov and R. Panigrahy
[Abstract]
In this paper we introduce a new notion of distance between nodes in a graph that we refer to as robust connectivity . Robust connectivity between a pair of nodes $u$ and $v$ is parameterized by a threshold $\kappa$ and intuitively captures the number of paths between $u$ and $v$ of length at most $\kappa$. Using this new notion of distances, we show that any black box algorithm for constructing a spanner can be used to construct a spectral sparsifier. We show that given an undirected weighted graph $G$, simply taking the union of spanners of a few (polylogarithmically many) random subgraphs of $G$ obtained by sampling edges at different probabilities, after appropriate weighting, yields a spectral sparsifier of $G$. We show how this be done in $\tilde O(m)$ time, producing a sparsifier with $\tilde O(n/\epsilon^2)$ edges. While the cut sparsifiers of Benczur and Karger are based on weighting edges according to (inverse) strong connectivity, and the spectral sparsifiers are based on resistance, our method weights edges using the robust connectivity measure. The main property that we use is that this new measure is always greater than the resistance when scaled by a factor of $O(\kappa)$ ($\kappa$ is chosen to be $O(\log n)$), but, just like resistance and connectivity, has a bounded sum, i.e. $\tilde O(n)$, over all the edges of the graph.

On the communication and streaming complexity of maximum bipartite matching, SODA 2012
A. Goel, M. Kapralov and S. Khanna
[Abstract]
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\subseteq E_A\cup 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-\epsilon)$ times the maximum matching in $G_A\cup 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-\epsilon$-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 $\frac{1}{2}$-approximation was known for both these problems.
In order to study these questions, we introduce the concept of an $\epsilon$-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 $\epsilon n$ error. We give a polynomial time construction of a $\frac{1}{2}$-matching cover of size $O(n)$ with some crucial additional properties, thereby showing that Alice and Bob can achieve a $\frac{2}{3}$-approximation with a message of size $O(n)$. While we do not provide bounds on the size of $\epsilon$-matching covers for $\epsilon<1/2$, we prove that in general, the size of the smallest $\epsilon$-matching cover of a graph $G$ on $n$ vertices is essentially equal to the size of the largest so-called $\epsilon$-Ruzsa Szemeredi graph on $n$ vertices. We use this connection to show that for any $\delta>0$, a $(\frac{2}{3}+\delta)$-approximation requires a communication complexity of $n^{1+\Omega(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 $\frac{3}{4}$-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- \frac{1}{e})$-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem. We present here the first deterministic one-pass streaming $(1-\frac{1}{e})$-approximation algorithm using $O(n)$ space for this setting.

Prediction strategies without loss, NIPS 2011
M. Kapralov and R. Panigrahy
[Abstract]
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 $5\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.
The algorithm extends to the general setting of $N$ experts, yielding 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 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.

Multiplicative approximations of random walk transition probabilities, APPROX 2011
M. Kapralov and R. Panigrahy
[Abstract]
We study the space and time complexity of approximating distributions of $l$-step random walks in simple (possibly directed) graphs $G$. While very efficient algorithms for obtaining additive $\epsilon$-approximations have been developed in the literature, no non-trivial results with multiplicative guarantees are known, and obtaining such approximations is the main focus of this paper. Specifically, we ask the following question: given a bound $S$ on the space used, what is the minimum threshold $t>0$ such that $l$-step transition probabilities for all pairs $u, v\in V$ such that $P_{uv}^l\geq t$ can be approximated within a $1\pm \epsilon$ factor? How fast can an approximation be obtained?
We show that the following surprising behavior occurs. When the bound on the space is $S=o(n^2/d)$, where $d$ is the minimum out-degree of $G$, no approximation can be achieved for non-trivial values of the threshold $t$. However, if an extra factor of $s$ space is allowed, i.e. $S=\tilde \Omega(sn^2/d)$ space, then the threshold $t$ is exponentially small in the length of the walk $l$ and even very small transition probabilities can be approximated up to a $1\pm \epsilon$ factor. One instantiation of these guarantees is as follows: any almost regular directed graph can be represented in $\tilde O(l n^{3/2+\epsilon})$ space such that all probabilities larger than $n^{-10}$ can be approximated within a $(1\pm \epsilon)$ factor as long as $l\geq 40/\epsilon^2$. Moreover, we show how to estimate of such probabilities faster than matrix multiplication time.
For undirected graphs, we also give small space oracles for estimating $P^l_{uv}$ using a notion of bicriteria approximation based on approximate distance oracles of Thorup and Zwick [STOC'01].

Improved bounds for online stochastic matching, ESA 2010
B. Bahmani and M. Kapralov
[Abstract]
We study the online stochastic matching problem in a form motivated by Internet display advertisement. Recently, Feldman et al. gave an algorithm that achieves $0.6702$ competitive ratio, thus breaking through the $1-1/e$ barrier. One of the questions left open in their work is to obtain a better competitive ratio by generalizing their two suggested matchings (TSM) algorithm to $d$-suggested matchings ($d$-SM).
We show that the best competitive ratio that can be obtained with the static analysis used in the $d$-SM algorithm is upper bounded by $0.76$, even for the special case of $d$-regular graphs, thus suggesting that a dynamic analysis may be needed to improve the competitive ratio significantly. We make the first step in this direction by showing that the RANDOM algorithm, which assigns an impression to a randomly chosen eligible advertiser, achieves $1-e^{-d}d^d/d!=1-O(1/\sqrt{d})$ competitive ratio for $d$-regular graphs, which converges to $1$ as $d$ increases. On the hardness side, we improve the upper bound of $0.989$ on the competitive ratio of any online algorithm obtained by Feldman et al. to $1-1/(e+e^2)\approx 0.902$. Finally, we show how to modify the TSM algorithm to obtain an improved $0.699$ approximation for general bipartite graphs.

Perfect matchings in O(n log n) time in regular bipartite graphs , STOC 2010 (invited to SICOMP special issue for STOC 2010 papers)
A. Goel, M. Kapralov and S. Khanna
[Abstract]
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\sqrt{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 algorithm was improved first to $\tilde O\left(\min\{m, n^{2.5}/d\}\right)$ and then to $\tilde O\left(\min\{m, n^2/d\}\right)$. It was also shown that the latter algorithm is optimal up to polylogarithmic factors among all algorithms that use non-adaptive uniform sampling to reduce the size of the graph as a first step.
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 random walk on a modified graph 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 $\Omega(nd)$ lower bound for any deterministic algorithm. 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.

Graph sparsification via refinement sampling, manuscript, 2009
A. Goel, M. Kapralov and S. Khanna

Perfect matchings in Õ(n^1.5) time in regular bipartite graphs, submitted, 2009
A. Goel, M. Kapralov and S. Khanna
[Abstract]
We consider the well-studied problem of finding a perfect matching in $d$-regular bipartite graphs with $2n$ vertices and $m = nd$ edges. While the best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes $O(m \sqrt{n})$ time, in regular bipartite graphs, a perfect matching is known to be computable in $O(m)$ time. Very recently, the $O(m)$ bound was improved to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$ expected time, an expression that is bounded by $\tilde{O}(n^{1.75})$. In this paper, we further improve this result by giving an $O(\min\{m, \frac{n^2\ln^3 n}{d}\})$ expected time algorithm for finding a perfect matching in regular bipartite graphs; as a function of $n$ alone, the algorithm takes expected time $O((n\ln n)^{1.5})$.
To obtain this result, we design and analyze a two-stage sampling scheme that reduces the problem of finding a perfect matching in a regular bipartite graph to the same problem on a subsampled bipartite graph with $O(n\ln n)$ edges. The first-stage is a sub-linear time uniform sampling that reduces the size of the input graph while maintaining certain structural properties of the original graph. The second-stage is a non-uniform sampling that takes linear-time (on the reduced graph) and outputs a graph with $O(n\ln n)$ edges, while preserving a matching with high probability. This matching is then recovered using the Hopcroft-Karp algorithm. While the standard analysis of Hopcroft-Karp also gives us an $\tilde{O}(n^{1.5})$ running time, we present a tighter analysis for our special case that results in the stronger $\tilde{O}(\min\{m, \frac{n^2}{d} \})$ time mentioned earlier.
Our proof of correctness of this sampling scheme uses a new correspondence theorem between cuts and Hall's theorem ``witnesses'' for a perfect matching in a bipartite graph that we prove. We believe this theorem may be of independent interest; as another example application, we show that a perfect matching in the support of an $n \times n$ doubly stochastic matrix with $m$ non-zero entries can be found in expected time $\tilde{O}(m + n^{1.5})$.

Factor Modeling for Advertisement Targeting, NIPS 2009
Y. Chen, M. Kapralov, D. Pavlov, J. Canny
[Abstract]
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 posi- tional 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 Yahoo's 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.

Perfect matchings via uniform sampling in regular bipartite graphs, SODA 2009 (full version in TALG special issue for SODA 2009 papers)
A. Goel, M. Kapralov and S. Khanna
[Abstract]
In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to König's work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ is the number of vertices, and $d$ is the degree of each node). The currently most efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and Schirra. We improve this running time to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$; this minimum can never be larger than $O(n^{1.75}\sqrt{\ln n})$. We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a $d$-regular bipartite graph independently with a probability $p = O(\frac{n\ln n}{d^2})$ then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the $O(m\sqrt{n})$ algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to $\ln^2 n$).

Pre-PhD work on imaging:

On the study of 1PI algorithms for a general class of curves, SIAM Journal on Imaging Sciences, Volume 1, Issue 4, pp. 418-459 (2008).
M. Kapralov, A. Katsevich

Theoretically exact FBP reconstruction algorithms for two general classes of curves, 9th International Meeting on Fully Three-Dimensional Image Reconstruction in Radiology and Nuclear Medicine (Fully3D) 2007, Best paper award in CT.
A. Katsevich, M. Kapralov

Filtered backprojection inversion of the cone beam transform for a general class of curves, SIAM Journal on Applied Mathematics, Volume 68, Issue 2, pp. 334-353 (2007)
A. Katsevich, M. Kapralov

A 1PI algorithm for helical trajectories that violate the convexity condition, Inverse Problems, Volume 22, No 6 (December 2006) 2123-2143, Institute of Physics (IoP) Select article
M. Kapralov, A. Katsevich