Research
I am broadly interested in the design of efficient algorithms. Most of my current work is on designing models that consume little space and/or can be applied in a scalable manner.
Interested in working with me? Apply to the EPFL EDIC PhD program and mention my name on your application. For undergraduate summer internships, see Summer@EPFL.
Postdoctoral opportunities: see the Theory Group’s current call.
Selected recent work
Towards Tight Bounds for Streaming Attention
SODA 2027 (to appear)
Algorithms and lower bounds for memory-efficient attention and KV-cache compression.
[Abstract]
The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In particular, the classical transformer architecture explicitly stores all previously seen input elements (tokens) in order to generate the next one. The problem of implementing a transformer in limited space, known as KV cache compression, has received much interest over the past few years, spurring the development of powerful heuristics. Recent works of Haris et al, COLT'25 and Kochetkova et al, NeurIPS'25, formalized KV cache compression as the streaming attention approximation problem, providing both upper bounds (based on discrepancy theory) and information theoretic lower bounds. However, those papers left open a significant gap between the upper and lower bounds. For example, the space usage of their algorithms increases with the precision parameter, but the lower bound does not get stronger.
In this work, we revisit the streaming attention approximation problem and provide nearly tight bounds on its space complexity. On the algorithmic side, we achieve the result through a surprisingly tight interplay between three distinct methods for kernel density estimation: discrepancy-based coreset constructions (e.g., Charikar-Kapralov-Waingarten'24), the polynomial method (e.g., Greengard-Rokhlin'87, Alman-Song'23), and space partitioning (e.g., Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). On the lower bound side, our main technical contribution is a new technique for using the INDEX problem with a large amount of side information that we hope will prove useful in other high dimensional geometric estimation problems.
DASHQuant: Provable Quantization with a Single Randomized Hadamard Transform
NeurIPS 2026 (to appear)
Fast vector quantization with provable error guarantees using a single randomized Hadamard transform.
[Abstract]
Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require $\Theta(d^2)$ time. The randomized Hadamard transform $HD$ reduces this cost to $O(d \log d)$, but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we introduce DASHQuant (Dithered Accelerated Single-Hadamard Quantization), a provable variant of this approach. Specifically, the quantizer applies $HD$ to the input vector and adds a random dithering before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant, and a special case of EDEN, achieves mean squared error $\bigl(\pi\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}$ at $b$ bits per coordinate, where the $o(1)$ term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.
Streaming Attention Approximation via Discrepancy Theory
NeurIPS 2025 · Spotlight
BalanceKV: a streaming approach to attention approximation with theoretical guarantees and empirical evaluation.
[Abstract]
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.
Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
ICLR 2025
Subquadratic kernel matrix–vector multiplication under sparsity assumptions, motivated by fast attention.
[Abstract]
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. We obtain the first subquadratic-time algorithm that works under this assumption, for unrestricted vectors.
Courses, seminars, schools
- We are organizing the Turing Course, which introduces high school students to some of the gems of computer science.
- Theory Seminar and Theory Coffee
- Foundations of Deep Learning reading group
- Swiss Winter School — ~biennial Winter School on TCS.
People
I have been fortunate to advise or co-advise the following PhD students and postdocs. For former members, parentheses give the first position after EPFL.
Current PhD students
Former students and postdocs
- Kshiteej Sheth (AI Research Scientist at JPMorganChase, New York)PhD 2026
- Mikhail Makarov (Amazon)PhD 2025
- Paritosh Garg (Snowflake)PhD 2022
- Grzegorz Gluch (postdoc at UC Berkeley)
- Yu Chen (Assistant Professor at the National University of Singapore)
- Akash Kumar (Assistant Professor at IIT Bombay)
- Marek Elias (Assistant Professor at Bocconi)
- Jakab Tardos (Google Zurich)
- Navid Nouri (BlockTech B.V.)
- Ashish Chiplunkar (Assistant Professor at IIT Delhi)
- Aida Mousavifar (Google Zurich)
- Ameya Velingker (Senior Research Scientist at Google Mountain View)
- Amir Zandieh (Research Scientist at Google Zurich)
Teaching
Algorithms II (CS-450) · Fall 2026
Previous courses and lecture notes
-
Topics in Theoretical Computer Science (Fall 2020)
-
Advanced Algorithms (Spring 2021, Spring 2020)
-
Sublinear Algorithms for Big Data Analysis (Fall 2021, Spring 2019, Spring 2018)
-
Topics in Theoretical Computer Science (Spring 2017)
-
Mini-course on streaming algorithms at the school Recent Advances in Algorithms, May 2017, St. Petersburg (Lecture 1, Lecture 2, Lecture 3, Lecture 4)
-
Sparse FFT mini-course at St. Petersburg Computer Science Center, November 14-15 2015, St. Petersburg, Russia (Lecture 1, Lecture 2, Lecture 3, Lecture 4)
-
MADALGO Summer School on Streaming Algorithms August 10-13 2015, Aarhus University, Denmark (Lecture 1, Lecture 2, Lecture 3)
-
6.046 Design and Analysis of Algorithms, Spring 2014, MIT
Program committees
SODA 2026, ITCS 2026, FOCS 2025, RANDOM 2025, SODA 2025, ITCS 2025, ICALP 2024, SOSA 2023, STOC 2022, RANDOM 2021, ICALP 2021, CSR 2021, SOSA 2021, ESA 2020, HALG 2020, SODA 2020, PODS 2019, FSTTCS 2018, ICALP 2017, FOCS 2015.
About
I completed my PhD at Stanford iCME, where I was advised by Ashish Goel. After graduating from Stanford I spent two years as a postdoc at the Theory of Computation Group at MIT CSAIL, working with Piotr Indyk, and then a year at the IBM T. J. Watson Research Center as a Herman Goldstine Postdoctoral Fellow.
I am grateful to the European Research Council for their generous support (ERC Starting Grant SUBLINEAR, 2018-2023).
Publications
-
Towards Tight Bounds for Streaming Attention, to appear in SODA 2027J. Chen, Y. Feng, P. Indyk, M. Kapralov, E. Kochetkova, B. Prokhorov
[Abstract]
The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In particular, the classical transformer architecture explicitly stores all previously seen input elements (tokens) in order to generate the next one. The problem of implementing a transformer in limited space, known as KV cache compression, has received much interest over the past few years, spurring the development of powerful heuristics. Recent works of Haris et al, COLT'25 and Kochetkova et al, NeurIPS'25, formalized KV cache compression as the streaming attention approximation problem, providing both upper bounds (based on discrepancy theory) and information theoretic lower bounds. However, those papers left open a significant gap between the upper and lower bounds. For example, the space usage of their algorithms increases with the precision parameter, but the lower bound does not get stronger.
In this work, we revisit the streaming attention approximation problem and provide nearly tight bounds on its space complexity. On the algorithmic side, we achieve the result through a surprisingly tight interplay between three distinct methods for kernel density estimation: discrepancy-based coreset constructions (e.g., Charikar-Kapralov-Waingarten'24), the polynomial method (e.g., Greengard-Rokhlin'87, Alman-Song'23), and space partitioning (e.g., Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). On the lower bound side, our main technical contribution is a new technique for using the INDEX problem with a large amount of side information that we hope will prove useful in other high dimensional geometric estimation problems.
-
DASHQuant: Provable Quantization with a Single Randomized Hadamard Transform, to appear in NeurIPS 2026 [MIT CSAIL News]Y. Feng, P. Indyk, M. Kapralov, D. Krachun, B. Prokhorov
[Abstract]
Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require $\Theta(d^2)$ time. The randomized Hadamard transform $HD$ reduces this cost to $O(d \log d)$, but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we introduce DASHQuant (Dithered Accelerated Single-Hadamard Quantization), a provable variant of this approach. Specifically, the quantizer applies $HD$ to the input vector and adds a random dithering before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant, and a special case of EDEN, achieves mean squared error $\bigl(\pi\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}$ at $b$ bits per coordinate, where the $o(1)$ term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.
-
M. Kapralov, L. Trevisan, W. Wrzos-Kaminska
[Abstract]
The problem of recovering planted community structure in random graphs has received a lot of attention in the literature on the stochastic block model, where the input is a random graph in which edges crossing between different communities appear with smaller probability than edges induced by communities. The communities themselves form a collection of vertex-disjoint sparse cuts in the expected graph, and can be recovered, often exactly, from a sample as long as a separation condition on the intra- and inter-community edge probabilities is satisfied.
In this paper, we ask whether the presence of a large number of overlapping sparsest cuts in the expected graph still allows recovery. For example, the $d$-dimensional hypercube graph admits $d$ distinct (balanced) sparsest cuts, one for every coordinate. Can these cuts be identified given a random sample of the edges of the hypercube where each edge is present independently with some probability $p\in (0, 1)$? We show that this is the case, in a very strong sense: the sparsest balanced cut in a sample of the hypercube at rate $p=C\log d/d$ for a sufficiently large constant $C$ is $1/\text{poly}(d)$-close to a coordinate cut with high probability. This is asymptotically optimal and allows approximate recovery of all $d$ cuts simultaneously. Furthermore, for an appropriate sample of hypercube-like graphs recovery can be made exact. The proof is essentially a strong hypercube cut sparsification bound that combines a theorem of Friedgut, Kalai and Naor on boolean functions whose Fourier transform concentrates on the first level of the Fourier spectrum with Karger's cut counting argument.
-
Spectral Clustering with Side Information, SODA 2026H. Fichtenberger, M. Kapralov, E. Kochetkova, S. Lattanzi, D. Mazzali, W. Wrzos-Kaminska
[Abstract]
In the graph clustering problem with a planted solution, the input is a graph on $n$ vertices partitioned into $k$ clusters, and the task is to infer the clusters from graph structure. A standard assumption is that clusters induce well-connected subgraphs (i.e. $\Omega(1)$-expanders), and connections between clusters are sparse (i.e. clusters form $\epsilon$-sparse cuts). Such a graph defines the clustering uniquely up to $\approx\epsilon$ misclassification rate, and efficient algorithms for achieving this rate are known. While this vanilla version of graph clustering is extremely well studied, in the practice of graph analysis vertices of the graph are typically equipped with labels, or features, that provide additional information on cluster ids of the vertices. For example, each vertex could be equipped with a cluster label that is corrupted independently with probability $\delta$. Using either of the two sources of information separately leads to misclassification rate $\min\{\epsilon,\delta\}$, but can one combine the two to achieve misclassification rate $\approx\epsilon\delta$?
In this paper, we give an affirmative answer to this question, and furthermore show that such a misclassification rate can be achieved in sublinear time in the number of vertices $n$. Our key algorithmic insight is a new observation on “spectrally ambiguous” vertices in a well-clusterable graph.
While our sublinear-time classifier achieves the nearly optimal $\approx\widetilde{O}(\epsilon\delta)$ misclassification rate, the approximate clusters that it outputs do not necessarily induce expanders in the graph $G$. In our second result, we give a polynomial-time algorithm for reweighting edges of the input graph from the original $(k,\epsilon,\Omega(1))$-clusterable instance to a $(k,\widetilde{O}(\epsilon\delta),\Omega(1))$-clusterable instance (for constant $k$), improving sparsity of cuts nearly optimally and preserving expansion properties of the communities – an algorithm for refining community structure of the input graph.
-
M. Kapralov, C. Musco and K. Sheth
[Abstract]
Hankel matrices are an important class of highly-structured matrices, arising across computational mathematics, engineering, and theoretical computer science. It is well-known that positive semidefinite (PSD) Hankel matrices are always approximately low-rank. In particular, a celebrated result of Beckermann and Townsend shows that, for any PSD Hankel matrix $H \in \mathbb{R}^{n \times n}$ and any $\epsilon > 0$, letting $H_k$ be the best rank-$k$ approximation of $H$, $\|H-H_k\|_F \leq \epsilon \|H\|_F$ for $k = O(\log n \log(1/\epsilon))$. As such, PSD Hankel matrices are natural targets for low-rank approximation algorithms. We give the first such algorithm that runs in sublinear time. In particular, we show how to compute, in $\polylog(n, 1/\epsilon)$ time, a factored representation of a rank-$O(\log n \log(1/\epsilon))$ Hankel matrix $\widehat{H}$ matching the error guarantee of Beckermann and Townsend up to constant factors. We further show that our algorithm is robust -- given input $H+E$ where $E \in \mathbb{R}^{n \times n}$ is an arbitrary non-Hankel noise matrix, we obtain error $\|H - \widehat{H}\|_F \leq O(\|E\|_F) + \epsilon \|H\|_F$. Towards this algorithmic result, our first contribution is a structure-preserving existence result - we show that there exists a rank-$k$ Hankel approximation to $H$ matching the error bound of Beckermann and Townsend. Our result can be interpreted as a finite-dimensional analog of the widely applicable AAK theorem, which shows that the optimal low-rank approximation of an infinite Hankel operator is itself Hankel. Armed with our existence result, and leveraging the well-known Vandermonde structure of Hankel matrices, we achieve our sublinear time algorithm using a sampling-based approach that relies on universal ridge leverage score bounds for Vandermonde matrices.
-
Spectral clustering in birthday paradox time, SODA 2026M. Kapralov, E. Kochetkova and W. Wrzos-Kaminska
[Abstract]
Given a vertex in a $(k, \varphi, \epsilon)$-clusterable graph, i.e. a graph whose vertex set can be partitioned into a disjoint union of $\varphi$-expanders of size $\approx n/k$ with outer conductance bounded by $\epsilon$, can one quickly tell which cluster it belongs to? This is a classical question going back to the expansion testing problem of Goldreich and Ron’11 (the case of $k = 2$) that has received a lot of attention in the literature. For $k = 2$ a sample of $\approx n^{1/2+O(\epsilon/\varphi^2)}$ logarithmic length walks from a given vertex approximately determines its cluster membership by the birthday paradox: two vertices whose random walk samples are ‘close’ are likely in the same cluster, and otherwise in different clusters.
The study of the general case $k > 2$ was initiated by Czumaj, Peng and Sohler [STOC’15], and the works of Chiplunkar et al. [FOCS’18], Gluch et al. [SODA’21] showed that $\approx \mathrm{poly}(k) \cdot n^{1/2+O(\epsilon/\varphi^2)}$ random walk samples, and the same query time, suffices for general $k$. This matches the $k = 2$ result up to polynomial factors in $k$, but one notices a conceptual inconsistency: if the birthday paradox is indeed the phenomenon guiding the query complexity here, then the query complexity should decrease, as opposed to increase, with the number of clusters $k$! Since clusters have size $\approx n/k$, we expect to need $\approx (n/k)^{1/2+O(\epsilon/\varphi^2)}$ random walk samples, which gets smaller when $k$ gets larger, and reduces to constant when $k \approx n$. The currently best known query time (of Gluch et al. [SODA’21]), however, increases with $k$ due to computationally heavy linear-algebraic post-processing of random walk samples.
In this paper we design a novel representation of vertices in a $(k, \varphi, \epsilon)$-clusterable graph by a mixture of samples of logarithmic length walks. This representation not only uses the optimal $\approx (n/k)^{1/2+O(\epsilon/\varphi^2)}$ number of walks per vertex, but also allows for fast nearest neighbor search: given a collection of $\approx k$ vertices representing the clusters, and a query vertex $x$, we can find the cluster of $x$, using nearly linear time in the representation size of $x$. This gives a spectral clustering oracle with query time $\approx (n/k)^{1/2+O(\epsilon/\varphi^2)}$ and space complexity $k \cdot (n/k)^{1/2+O(\epsilon/\varphi^2)}$, matching the birthday paradox bound.
-
Streaming Attention Approximation via Discrepancy Theory, NeurIPS 2025 (Spotlight Paper)E. Kochetkova, K. Sheth, I. Han, A. Zandieh, M. Kapralov
[Abstract]
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.
-
S. Jiang, M. Kapralov, L. Er Lu and A. Sidford
[Abstract]
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 >0$ governing whether the flow is increased or decreased as it crosses edge $e$. We provide a randomized $\tilde{O}( (m + n^{1.5}) \cdot \mathrm{polylog}(\frac{W}{\delta}))$ 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 $\tilde{O}(m \sqrt{n} \cdot \log^2(\frac{W}{\delta}) )$ time algorithm, obtained by combining the algorithm of [Daitch-Spielman, 2008] with techniques from [Lee-Sidford, 2014]. 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 [Brand-Lee-Liu-Saranurak-Sidford-Song-Wang, 2021].
-
M.Kapralov, A. Kumar, S. Lattanzi, A. Mousavifar, W. Wrzos-Kaminska
[Abstract]
Testing graph cluster structure has been a central object of study in property testing since the foundational work of Goldreich and Ron [STOC'96] on expansion testing, i.e. the problem of distinguishing between a single cluster (an expander) and a graph that is far from a single cluster. More generally, a $(k, \epsilon)$-clusterable graph $G$ is a graph whose vertex set admits a partition into $k$ induced expanders, each with outer conductance bounded by $\epsilon$. A recent line of work initiated by Czumaj, Peng and Sohler [STOC'15] has shown how to test whether a graph is close to $(k, \epsilon)$-clusterable, and to locally determine which cluster a given vertex belongs to with misclassification rate $\approx \epsilon$, but no sublinear time algorithms for learning the structure of inter-cluster connections are known. As a simple example, can one locally distinguish between the `cluster graph' forming a line and a clique?
In this paper, we consider the problem of testing the hierarchical cluster structure of $(k, \epsilon)$-clusterable graphs in sublinear time. Our measure of hierarchical clusterability is the well-established Dasgupta cost, and our main result is an algorithm that approximates Dasgupta cost of a $(k, \epsilon)$-clusterable graph in sublinear time, using a small number of randomly chosen seed vertices for which cluster labels are known. Our main result is an $O(\sqrt{\log k})$ approximation to Dasgupta cost of $G$ in $\approx n^{1/2+O(\epsilon)}$ time using $\approx n^{1/3}$ seeds, effectively giving a sublinear time simulation of the algorithm of Charikar and Chatziafratis [SODA'17] on clusterable graphs. To the best of our knowledge, ours is the first result on approximating the hierarchical clustering properties of such graphs in sublinear time.
-
M. Kapralov, M. Makarov, C. Sohler
[Abstract]
Locality-sensitive hashing [Indyk,Motwani'98] is a classical data structure for approximate nearest neighbor search. It allows, after a close to linear time preprocessing of the input dataset, to find an approximately nearest neighbor of any fixed query in sublinear time in the dataset size. The resulting data structure is randomized and succeeds with high probability for every fixed query.
In many modern applications of nearest neighbor search the queries are chosen adaptively. In this paper, we study the robustness of the locality-sensitive hashing to adaptive queries in Hamming space. We present a simple adversary that can, under mild assumptions on the initial point set, provably find a query to the approximate near neighbor search data structure that the data structure fails on. Crucially, our adaptive algorithm finds the hard query exponentially faster than random sampling.
-
Best Paper at ICML 2024 workshop on Long Context Foundation ModelsP. Indyk, M. Kapralov, K. Sheth, T. Wagner
[Abstract]
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. We obtain the first subquadratic-time algorithm that works under this assumption, for unrestricted vectors.
-
A. Bhaskara, A. Jha, M. Kapralov, N. Manoj, D. Mazzali and W. Wrzos-Kaminska
[Abstract]
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 certain 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 classes 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 these classes spectral bisection with the normalized Laplacian 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.
-
Y. Chen, M. Kapralov, M. Makarov, D. Mazzali
[Abstract]
In this paper we study the problem of finding $(\epsilon, \phi)$-expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions. The goal is to partition the vertex set so that every component induces a $\phi$-expander, while the number of inter-cluster edges is only an $\epsilon$ fraction of the total volume. It was recently shown that there exists a simple algorithm to construct a $(O(\phi \log n), \phi)$-expander decomposition of an $n$-vertex graph using $\widetilde{O}(n/\phi^2)$ bits of space [Filtser, Kapralov, Makarov, ITCS'23]. This result calls for understanding the extent to which a dependence in space on the sparsity parameter $\phi$ is inherent. We move towards answering this question on two fronts. We prove that a $(O(\phi \log n), \phi)$-expander decomposition can be found using $\widetilde{O}(n)$ space, for every $\phi$. At the core of our result is the first streaming algorithm for computing boundary-linked expander decompositions, a recently introduced strengthening of the classical notion [Goranci et al., SODA'21]. The key advantage is that a classical sparsifier [Fung et al., STOC'11], with size independent of $\phi$, preserves the cuts inside the clusters of a boundary-linked expander decomposition within a multiplicative error. Notable algorithmic applications use sequences of expander decompositions, in particular one often repeatedly computes a decomposition of the subgraph induced by the inter-cluster edges (e.g., the seminal work of Spielman and Teng on spectral sparsifiers [Spielman, Teng, SIAM Journal of Computing 40(4)], or the recent maximum flow breakthrough [Chen et al., FOCS'22], among others). We prove that any streaming algorithm that computes a sequence of $(O(\phi \log n), \phi)$-expander decompositions requires ${\widetilde{\Omega}}(n/\phi)$ bits of space, even in insertion only streams.
-
C. Jin, M. Kapralov, S. Mahabadi, A. Vakilian
[Abstract]
We study the $k$-connectivity augmentation problem ($k$-CAP) in the single-pass streaming model. Given a $(k-1)$-edge connected graph $G=(V,E)$ that is stored in memory, and a stream of weighted edges $L$ with weights in $\{0,1,\dots,W\}$, the goal is to choose a minimum weight subset $L'\subseteq L$ such that $G'=(V,E\cup L')$ is $k$-edge connected. We give a $(2+\epsilon)$-approximation algorithm for this problem which requires to store $O(\epsilon^{-1} n\log n)$ words. Moreover, we show our result is tight: Any algorithm with better than $2$-approximation for the problem requires $\Omega(n^2)$ bits of space even when $k=2$. This establishes a gap between the optimal approximation factor one can obtain in the streaming vs the offline setting for $k$-CAP.
We further consider a natural generalization to the fully streaming model where both $E$ and $L$ arrive in the stream in an arbitrary order. We show that this problem has a space lower bound that matches the best possible size of a spanner of the same approximation ratio. Following this, we give improved results for spanners on weighted graphs: We show a streaming algorithm that finds a $(2t-1+\epsilon)$-approximate weighted spanner of size at most $O(\epsilon^{-1} n^{1+1/t}\log n)$ for integer $t$, whereas the best prior streaming algorithm for spanner on weighted graphs had size depending on $\log W$. Using our spanner result, we provide an optimal $O(t)$-approximation for $k$-CAP in the fully streaming model with $O(nk + n^{1+1/t})$ words of space.
Finally we apply our results to network design problems such as Steiner tree augmentation problem (STAP), $k$-edge connected spanning subgraph ($k$-ECSS), and the general Survivable Network Design problem (SNDP). In particular, we show a single-pass $O(t\log k)$-approximation for SNDP using $O(kn^{1+1/t})$ words of space, where $k$ is the maximum connectivity requirement.
-
M. Charikar, M. Kapralov, E. Waingarten
[Abstract]
In the kernel density estimation (KDE) problem one is given a kernel $K(x, y)$ and a dataset $P$ of points in a Euclidean space, and must prepare a data structure that can quickly answer density queries: given a point $q$, output a $(1+\epsilon)$-approximation to $\mu:=\frac1{|P|}\sum_{p\in P} K(p, q)$. The classical approach to KDE is the celebrated fast multipole method of [Greengard and Rokhlin]. The fast multipole method combines a basic space partitioning approach with a multidimensional Taylor expansion, which yields a $\approx \log^d (n/\epsilon)$ query time (exponential in the dimension $d$). A recent line of work initiated by [Charikar and Siminelakis] achieved polynomial dependence on $d$ via a combination of random sampling and randomized space partitioning, with [Backurs et al.] giving an efficient data structure with query time $\approx \mathrm{poly}{\log(1/\mu)}/\epsilon^2$ for smooth kernels.
Quadratic dependence on $\epsilon$, inherent to the sampling methods, is prohibitively expensive for small $\epsilon$. This issue is 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]. The work of Phillips and Tai gives a space efficient data structure with query complexity $\approx 1/(\epsilon \mu)$. This is polynomially better in $1/\epsilon$, but exponentially worse in $1/\mu$. We achieve the best of both: a data structure with $\approx \mathrm{poly}{\log(1/\mu)}/\epsilon$ 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.
-
S. Assadi, M. Kapralov, H. Yu
[Abstract]
Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applications in streaming, distributed computing, and massively parallel algorithms, among others. Graph sketching has proven to be quite successful for various problems such as connectivity, minimum spanning trees, edge or vertex connectivity, and cut or spectral sparsifiers. Yet, the problem of approximating shortest path metric of a graph, and specifically computing a spanner, is notably missing from the list of successes. This has turned the status of this fundamental problem into one of the most longstanding open questions in this area.
We present a partial explanation of this lack of success by proving a strong lower bound for a large family of graph sketching algorithms that encompasses prior work on spanners and many (but importantly not also all) related cut-based problems mentioned above. Our lower bound matches the algorithmic bounds of the recent result of Filtser, Kapralov, and Nouri (SODA'21), up to lower order terms, for constructing spanners via the same graph sketching family. This establishes near-optimality of these bounds, at least restricted to this family of graph sketching techniques, and makes progress on a conjecture posed in this latter work.
-
Expander Decomposition in Dynamic Streams, ITCS 2023A. Filtser, M. Kapralov, M. Makarov
[Abstract]
In this paper we initiate the study of expander decompositions of a graph $G=(V, E)$ in the streaming model of computation. The goal is to find a partitioning $\mathcal{C}$ of vertices $V$ such that the subgraphs of $G$ induced by the clusters $C \in \mathcal{C}$ are good expanders, while the number of intercluster edges is small. Expander decompositions are classically constructed by a recursively applying balanced sparse cuts to the input graph. In this paper we give the first implementation of such a recursive sparsest cut process using small space in the dynamic streaming model.
Our main algorithmic tool is a new type of cut sparsifier that we refer to as a power cut sparsifier - it preserves cuts in any given vertex induced subgraph (or, any cluster in a fixed partition of $V$) to within a $(\delta, \epsilon)$-multiplicative/additive error with high probability. The power cut sparsifier uses $\tilde{O}(n/\epsilon\delta)$ space and edges, which we show is asymptotically tight up to polylogarithmic factors in $n$ for constant $\delta$.
-
M. Kapralov, H. Lawrence, M. Makarov, C. Musco and K. Sheth
[Abstract]
We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix $T \in \mathbb{R}^{d \times d}$. In particular, for any integer rank $k \leq d$ and $\epsilon,\delta > 0$, our algorithm makes $\tilde{O} \left (k^2 \cdot \log(1/\delta) \cdot \text{poly}(1/\epsilon) \right )$ queries to the entries of $T$ and outputs a rank $\tilde{O} \left (k \cdot \log(1/\delta)/\epsilon\right )$ matrix $\tilde{T} \in \mathbb{R}^{d \times d}$ such that $\| T - \tilde{T}\|_F \leq (1+\epsilon) \cdot \|T-T_k\|_F + \delta \|T\|_F$. Here, $\|\cdot\|_F$ is the Frobenius norm and $T_k$ is the optimal rank-$k$ approximation to $T$, given by projection onto its top $k$ eigenvectors. $\tilde{O}(\cdot)$ hides $\text{polylog}(d) $ factors. Our algorithm is structure-preserving, in that the approximation $\tilde{T}$ 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 $\tilde{T}$ 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.
-
M. Kapralov, A. Kumar, S. Lattanzi and A. Mousavifar
[Abstract]
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, \epsilon)$-clusterable graphs, which are graphs that can be partitioned into $k$ induced expanders with outer conductance bounded by $\epsilon \ll 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 $\epsilon \ll 1$, provide query access to an $O(\epsilon \log k)$-approximation to this ground truth clustering in time $\approx 2^{\mathrm{poly}(k/\epsilon)} n^{1/2+O(\epsilon)}$ per query.
Motivated by the rising interest in learning hierarchical structures in large networks, in this paper we introduce $(k, \gamma)$-hierarchically clusterable graphs, a natural hierarchical analog of classical $(k, \epsilon)$-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 $\approx \mathrm{poly}(k) \cdot n^{1/2+O(\gamma)}$ 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.
-
K. Bringmann, M. Kapralov, M. Makarov, V. Nakos, A. Yagudin and A. Zandieh
[Abstract]
We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier $k$-sparse vector $\widehat{x} \in \mathbb{C}^{n^d}$ 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 on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT 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 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 this task, and (b) evidence that a strongly subquadratic time for Sparse FT via this approach is likely impossible. We achieve the latter by proving a conditional quadratic time lower bound on sparse polynomial multipoint evaluation (the classical non-equispaced sparse FT) 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 $\ell_2$ noise. This requires proving new structural properties of the recently introduced adaptive aliasing filters combined with a variety of new techniques and ideas.
-
Motif Cut Sparsifiers, FOCS 2022M. Kapralov, M. Makarov, S. Silwal, C. Sohler and J. Tardos
[Abstract]
A motif is a frequently occurring subgraph of a given directed or undirected graph $G$. 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. 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'$ with only $\widetilde{O}(n/\epsilon^2)$ edges such that for every cut, the weighted number of copies of $M$ crossing the cut in $G'$ 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 work of [Kar99] and [BK15] to the motif setting. We adapt the importance sampling framework through the viewpoint of hypergraph sparsification by deriving the edge sampling probabilities 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.
-
A. Chiplunkar, J. Kallaugher, M. Kapralov and E. Price
[Abstract]
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 the parity of some cycle in $G$ 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 $\ell$. 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.
-
Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems, to appear in IEEE Transactions on Parallel and Distributed SystemsM. Besta, M. Fischer, V. Kalavri, M. Kapralov, T. Hoefler
[Abstract]
Graph processing has become an important part of various areas of computing, including machine learning, medical applications, social network analysis, computational sciences, and others. A growing amount of the associated graph processing workloads are dynamic, with millions of edges added or removed per second. Graph streaming frameworks are specifically crafted to enable the processing of such highly dynamic workloads. Recent years have seen the development of many such frameworks. However, they differ in their general architectures (with key details such as the support for the concurrent execution of graph updates and queries, or the incorporated graph data organization), the types of updates and workloads allowed, and many others. To facilitate the understanding of this growing field, we provide the first analysis and taxonomy of dynamic and streaming graph processing. We focus on identifying the fundamental system designs and on understanding their support for concurrency, and for different graph updates as well as analytics workloads. We also crystallize the meaning of different concepts associated with streaming graph processing, such as dynamic, temporal, online, and time-evolving graphs, edge-centric processing, models for the maintenance of updates, and graph databases. Moreover, we provide a bridge with the very rich landscape of graph streaming theory by giving a broad overview of recent theoretical related advances, and by discussing which graph streaming models and settings could be helpful in developing more powerful streaming frameworks and designs. We also outline graph streaming workloads and research challenges.
-
M. Kapralov, A. Musipatla, J. Tardos, D. Woodruff, S. Zhou
[Abstract]
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of Gavinsky et. al. [STOC'07], has played an important role in the streaming lower bounds for graph problems such as triangle and subgraph counting, maximum matching, MAX-CUT, Schatten $p$-norm approximation, maximum acyclic subgraph, testing bipartiteness, $k$-connectivity, and cycle-freeness. The one-way communication complexity of the Boolean Hidden Matching problem on a universe of size $n$ is $\Theta(\sqrt{n})$, resulting in $\Omega(\sqrt{n})$ lower bounds for constant factor approximations to several of the aforementioned graph problems. The related (and, in fact, more general) Boolean Hidden Hypermatching (BHH) problem introduced by Verbin and Yu [SODA'11] provides an approach to proving higher lower bounds of $\Omega(n^{1-1/t})$ for integer $t\geq 2$. Reductions based on Boolean Hidden Hypermatching generate distributions on graphs with connected components of diameter about $t$, and basically show that long range exploration is hard in the streaming model of computation with adversarial arrivals.
In this paper we introduce a natural variant of the BHM problem, called noisy BHM (and its natural noisy BHH variant), that we use to obtain higher than $\Omega(\sqrt{n})$ lower bounds for approximating several of the aforementioned problems in graph streams when the input graphs consist only of components of diameter bounded by a fixed constant. We also use the noisy BHM problem to show that the problem of classifying whether an underlying graph is isomorphic to a complete binary tree in insertion-only streams requires $\Omega(n)$ space, which seems challenging to show using BHM or BHH alone.
-
Simulating Random Walks in Random Streams, SODA 2022J. Kallaugher, M. Kapralov and E. Price
[Abstract]
The random order graph streaming model has received significant attention recently, with problems such as matching size estimation, component counting, and the evaluation of bounded degree constant query testable properties shown to admit surprisingly space efficient algorithms.
The main result of this paper is a space efficient single pass random order streaming algorithm for simulating nearly independent random walks that start at uniformly random vertices. We show that the distribution of $k$-step walks from $b$ vertices chosen uniformly at random can be approximated up to error $\varepsilon$ per walk using $(1/\varepsilon)^{O(k)} 2^{O(k^2)}\cdot b$ words of space with a single pass over a randomly ordered stream of edges, solving an open problem of Peng and Sohler [SODA ’18]. Applications of our result include the estimation of the average return probability of the $k$-step walk (the trace of the $k^\text{th}$ power of the random walk matrix) as well as the estimation of PageRank. We complement our algorithm with a strong impossibility result for directed graphs.
-
Efficient and Local Parallel Random Walks, NeurIPS 2021M. Kapralov, S. Lattanzi, N. Nouri and J. Tardos
[Abstract]
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 (Lacki 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 walk 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.
-
M. Kapralov, R. Krauthgamer, J. Tardos and Y. Yoshida
[Abstract]
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^*(n)$ hyperedges, where $O^*$ 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.
-
M. Kapralov, R. Krauthgamer, J. Tardos and Y. Yoshida
[Abstract]
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 $\epsilon$-spectral sparsifier with $O^*(nr)$ hyperedges, where $O^*$ suppresses $(\epsilon^{-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+\epsilon)$-approximates all the cuts in a given hypergraph, and hence also on the bit complexity of every $\epsilon$-cut/spectral sparsifier. These lower bounds are based on Ruzsa-Szemerédi graphs, and a particular instantiation yields an $\Omega(nr)$ lower bound on the bit complexity even for fixed constant $\epsilon$. This is tight up to polylogarithmic factors in $n$, due to recent hypergraph cut sparsifiers of [Chen, Khanna and Nagda, FOCS'20].
Finally, for directed hypergraphs, we present an algorithm that computes an $\epsilon$-spectral sparsifier with $O^*(n^2r^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 $\Omega(n^2)$ hyperarcs.
-
M. Kapralov, G. Maystre and J. Tardos
[Abstract]
In this paper we revisit the problem of constructing randomized composable coresets for bipartite matching. In this problem the input graph is randomly partitioned across $k$ players, each of which sends a single message to a coordinator, who then must output a good approximation to the maximum matching in the input graph. Assadi and Khanna gave the first such coreset, achieving a $1/9$-approximation by having every player send a maximum matching, i.e. at most $n/2$ words per player. The approximation factor was improved to $1/3$ by Bernstein et al.
In this paper, we show that the matching skeleton construction of Goel, Kapralov and Khanna, which is a carefully chosen (fractional) matching, is a randomized composable coreset that achieves a $1/2-o(1)$ approximation using at most $n-1$ words of communication per player. We also show an upper bound of $2/3+o(1)$ on the approximation ratio achieved by this coreset.
-
M. Kapralov
[Abstract]
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\cdot \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 $\frac1{1+\ln 2}$-approximation [Epstein et al'STACS'12] and even a better than $(2-\sqrt{2})$-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 $\frac1{1+\ln 2}\approx 0.59$ requires $n^{1+\Omega(1/\log\log n)}\gg 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.
-
A. Filtser, M. Kapralov and N. Nouri
[Abstract]
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 $\lfloor\frac k2\rfloor+1$-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 $\widetilde{O}(n^{\frac23})$-spanner using $\widetilde{O}(n)$ space, and in general a $\widetilde{O}(n^{\frac23(1-\alpha)})$-spanner using $\widetilde{O}(n^{1+\alpha})$ space for every $\alpha\in [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 study the simultaneous communication model and propose the first protocols with low per player information.
-
G. Gluch, M. Kapralov, S. Lattanzi, A. Mousavifar and C. Sohler
[Abstract]
Given a graph $G$ that can be partitioned into $k$ disjoint expanders with outer conductance upper bounded by $\epsilon\ll 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(\epsilon)$ 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(\epsilon)})$ and preprocessing time $2^{O(\frac{1}{\epsilon} k^4 \log^2(k))} n^{1/2+O(\epsilon)}$ that provides misclassification error $O(\epsilon \log k)$ per cluster for any $\epsilon \ll 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(\epsilon)}$) -- 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 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.
-
M. Charikar, M. Kapralov, N. Nouri and P. Siminelakis
[Abstract]
In this paper we revisit the kernel density estimation problem: given a kernel $K(x, y)$ and a dataset of $n$ points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query $q$, a $(1+\epsilon)$-approximation to $\mu:=\frac1{|P|}\sum_{p\in 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 a 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 $\mu^{-(1+o(1))/4}$ and space complexity $\mu^{-(1+o(1))}$ for the Gaussian kernel. Our data dependent approach achieves query time $\mu^{-0.173-o(1)}$ and space $\mu^{-(1+o(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.
-
M. Kapralov, N. Nouri, I. Razenshteyn, A. Velingker and A. Zandieh
[Abstract]
Random binning features, introduced in the seminal paper of Rahimi and Recht (2007), are an efficient method for approximating a kernel matrix using locality sensitive hashing. Random binning features provide a very simple and efficient way of approximating the Laplace kernel but unfortunately do not apply to many important classes of kernels, notably ones that generate smooth Gaussian processes, such as the Gaussian kernel and Matern kernel. In this paper, we introduce a simple weighted version of random binning features and show that the corresponding kernel function generates Gaussian processes of any desired smoothness. We show that our weighted random binning features provide a spectral approximation to the corresponding kernel matrix, leading to efficient algorithms for kernel ridge regression. Experiments on large scale regression datasets show that our method outperforms the accuracy of random Fourier features method.
-
M. Kapralov, S. Mitrovic, A. Norouzi-Fard and J. Tardos
[Abstract]
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, on the one hand, 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, a surprisingly space efficient algorithm for processing the samples exists: $O(\log^2 n)$ bits of space suffice to compute an estimate.
Our main technical tool is a new peeling type algorithm for matching that we simulate using a recursive sampling process that crucially ensures that local neighborhood information from `dense' regions of the graph is provided at appropriately higher sampling rates. 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. The previous best result on matching size estimation from random samples was a $\log^{O(1)} n$ approximation [Kapralov et al'14].
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$ runtime. 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 $\widetilde{\Omega}(d^2)\gg O(d\log n)$ time for a worst case edge even for $d=\exp(\Theta(\sqrt{\log n}))$.
-
M. Elias, M. Kapralov, J. Kulkarni and Y. T. Lee
[Abstract]
We propose a $(\epsilon,\delta)$-differentially private mechanism that, given an input graph $G$ with $n$ vertices and $m$ edges, in polynomial time generates a synthetic graph $G'$ approximating all cuts of the input graph up to an additive error of $O\!\left(\sqrt{\frac{mn}{\epsilon}}\log^2\!\left(\frac{n}{\delta}\right)\right)$. 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 prominent 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.
-
T. D. Ahle, M. Kapralov, J. B. T. Knudsen, R. Pagh, A. Velingker, D. Woodruff and A. Zandieh(Merged version of this paper and this paper)
[Abstract]
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.
-
M. Kapralov, A. Mousavifar, C. Musco, C. Musco, N. Nouri, A. Sidford and J. Tardos(Merged version of this paper and this paper)
[Abstract]
In this paper, we resolve the complexity problem of spectral graph sparsification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses $\widetilde{O}(n)$ space, and with high probability, recovers a spectral sparsifier from the sketch in $\widetilde{O}(n)$ time. Prior results either achieved near optimal $\widetilde{O}(n)$ space, but $\Omega(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 $\widetilde{O}(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 $\widetilde{O}(n)$ time per evaluation. Our faster PRG is essential to simultaneously achieving near optimal space and time complexity.
-
Efficiently Learning Fourier Sparse Set Functions, NeurIPS 2019 (spotlight presentation)A. Amrollahi, A. Zandieh, M. Kapralov, A. Krause
[Abstract]
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.
-
Online Matching with General Arrivals, FOCS 2019B. Gamlath, M. Kapralov, A. Maggiori, O. Svensson, D. Wajc
[Abstract]
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 $\frac{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 $\frac{1}{2}$ competitive.
2. For general vertex arrivals, randomization helps --- there exists a randomized $(\frac{1}{2}+\Omega(1))$-competitive online matching algorithm.
-
M. Kapralov, D. Krachun
[Abstract]
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 $\epsilon > 0$, if one allows $\tilde{O}(n)$ space, a $(1+\epsilon)$-approximate solution to the MAX-CUT value can be obtained by storing an $\tilde{O}(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 $\Omega(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 $\Omega(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 $\ell_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 $\ell_1$ norm of the Fourier coefficients of the messages of individual players, and then argue, using the convolution theorem, that similar strong bounds on the $\ell_1$ norm are essentially preserved once messages of different players are combined.
-
H. Avron, M. Kapralov, C. Musco, C. Musco, A. Velingker and A. Zandieh
[Abstract]
Reconstructing continuous signals from a small number of discrete samples is a fundamental problem across science and engineering. In practice, we are often interested in signals with 'simple' Fourier structure, such as bandlimited, multiband, and Fourier sparse signals. More broadly, any prior knowledge about a signal's Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct.
We formalize this intuition by showing that, roughly, a continuous signal from a given class can be approximately reconstructed using a number of samples proportional to the statistical dimension of the allowed power spectrum of that class. Further, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction.
Surprisingly, we also show that, up to logarithmic factors, a universal non-uniform sampling strategy can achieve this optimal complexity for any class of signals. We present a simple and efficient algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art. At the same time, it gives the first computationally and sample efficient solution to a broad range of problems, including multiband signal reconstruction and kriging and Gaussian process regression tasks in one dimension.
Our work is based on a novel connection between randomized linear algebra and signal reconstruction with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in signal reconstruction. We believe that these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.
-
S. Assadi, M. Kapralov, S. Khanna
[Abstract]
In the subgraph counting problem, we are given a input graph $G(V, E)$ and a target graph $H$; the goal is to estimate the number of occurrences of $H$ in $G$. Our focus here is on designing sublinear-time algorithms for approximately counting occurrences of $H$ in $G$ in the setting where the algorithm is given query access to $G$. This problem has been studied in several recent papers which primarily focused on specific families of graphs $H$ such as triangles, cliques, and stars. However, not much is known about approximate counting of arbitrary graphs $H$. This is in sharp contrast to the closely related subgraph enumeration problem that has received significant attention in the database community as the database join problem. The AGM bound shows that the maximum number of occurrences of any arbitrary subgraph $H$ in a graph $G$ with $m$ edges is $O(m^{\rho(H)})$, where $\rho(H)$ is the fractional edge-cover of $H$, and enumeration algorithms with matching runtime are known for any $H$.
We bridge this gap between subgraph counting and subgraph enumeration by designing a sublinear-time algorithm that can estimate the number of any arbitrary subgraph $H$ in $G$, denoted by $\#H$, to within a $(1\pm \epsilon)$-approximation w.h.p. in $O(\frac{m^{\rho(H)}}{\#H}) \cdot poly(\log{n},1/\epsilon)$ time. Our algorithm is allowed the standard set of queries for general graphs, namely degree queries, pair queries and neighbor queries, plus an additional edge-sample query that returns an edge chosen uniformly at random. The performance of our algorithm matches those of Eden et.al. [FOCS 2015, STOC 2018] for counting triangles and cliques and extend them to all choices of subgraph $H$ under the additional assumption of edge-sample queries. We further show that our algorithm works for the more general database join size estimation problem and prove a matching lower bound for this problem.
-
M. Kapralov, A. Velingker, A. Zandieh
[Abstract]
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 $\mathbb{Z}_N$ or $\mathbb{Z}_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 $\text{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: (1) worst case support in Fourier domain with randomized coefficients and (2) random locations in Fourier domain with worst case coefficients. Our techniques lead to an $\widetilde O(k^2)$ time algorithm for the former and an $\widetilde O(k)$ time algorithm for the latter.
-
A. Chiplunkar, M. Kapralov, S. Khanna, A. Mousavifar and Y. Peres
[Abstract]
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 $\tilde{O}(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.
-
J. Kallaugher, M. Kapralov and E. Price
[Abstract]
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.
-
M. Kapralov
[Abstract]
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 $\approx 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 $\approx 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 $\omega(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).
-
M. Kapralov, J. Nelson, J. Pachocki, Z. Wang, D. Woodruff and M. Yahyazadeh
[Abstract]
In the communication problem $\mathbf{UR}$ (universal relation), Alice and Bob respectively receive $x, y \in\{0,1\}^n$ with the promise that $x\neq y$. The last player to receive a message must output an index $i$ such that $x_i\neq y_i$. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly $\Theta(\min\{n,\log(1/\delta)\log^2(\frac n{\log(1/\delta)})\})$ for failure probability $\delta$.
Our lower bound holds even if promised $\mathop{support}(y)\subset \mathop{support}(x)$. As a corollary, we obtain optimal lower bounds for $\ell_p$-sampling in strict turnstile streams for $0\le p < 2$, as well as for the problem of finding duplicates in a stream. Our lower bounds do not need to use large weights, and hold even if promised $x\in\{0,1\}^n$ at all points in the stream. We give two different proofs of our main result.
The first proof demonstrates that any algorithm $\mathcal 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 $\mathcal 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 $\mathcal A$, which is loosely motivated by techniques in differential privacy. Our correctness analysis involves understanding the ability of $\mathcal A$ to correctly answer adaptive queries which have positive but bounded mutual information with $\mathcal 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 \cite{MiltersenNSW98} which needs to interact with $\mathcal 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 $\mathcal A$ in the reduction.
-
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees, ICML 2017H. Avron, M. Kapralov, C. Musco, C. Musco, A. Velingker and A. Zandieh
[Abstract]
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. Qualitatively, our results are twofold: on one hand, we show that random Fourier feature approximation can provably speed up kernel ridge regression under reasonable assumptions.
At the same time, we show that the method is suboptimal, and sampling from a modified distribution in Fourier space, given by the leverage function of the kernel, yields provably better performance. We study this optimal sampling distribution for the Gaussian kernel, achieving a nearly complete characterization for the case of one-dimensional bounded datasets. Based on this characterization, we propose an efficient sampling scheme with guarantees superior to random Fourier features in this regime.
-
V. Cevher, M. Kapralov, J. Scarlett and A. Zandieh
[Abstract]
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].
These results are proved using non-adaptive algorithms, and the latter $O(k\log n)$ sample complexity result is essentially the best possible under the sparsity assumption alone: It is known that even adaptive algorithms must use $\Omega((k\log(n/k))/\log\log n)$ samples [Hassanieh et al., STOC'12]. By adaptive, we mean being able to exploit previous samples in guiding the selection of further samples.
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, where $k= k_0k_1$ is the total sparsity. Signals arising in applications are often well approximated by this model with $k_0\ll k$.
Our main result is the first sparse FFT algorithm for $(k_0, k_1)$-block sparse signals with the sample complexity of $O^*(k_0k_1 + k_0\log(1+ k_0)\log n)$ at constant signal-to-noise ratios, and sublinear runtime. A similar sample complexity was previously achieved in the works on {\em model-based compressive sensing} using random Gaussian measurements, but used $\Omega(n)$ runtime.
To the best of our knowledge, our result is the first sublinear-time algorithm for model based compressed sensing, and the first sparse FFT result that goes below the $O(k\log n)$ sample complexity bound. Interestingly, the aforementioned model-based compressive sensing result that relies on Gaussian measurements is non-adaptive, whereas our algorithm crucially uses {\em adaptivity} to achieve the improved sample complexity bound.
We prove that adaptivity is in fact necessary in the Fourier setting: Any non-adaptive algorithm must use $\Omega(k_0k_1\log \frac{n}{k_0k_1})$ samples for the $(k_0,k_1$)-block sparse model, ruling out improvements over the vanilla sparsity assumption. Our main technical innovation for adaptivity is a new randomized energy-based importance sampling technique that may be of independent interest.
-
M. Kapralov, S. Khanna, M. Sudan and A. Velingker
[Abstract]
We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. We show that there exists a constant $\epsilon_* > 0$ such that any randomized streaming algorithm that computes a $(1+\epsilon_*)$-approximation to MAX-CUT requires $\Omega(n)$ space on an $n$ vertex graph. By contrast, there are algorithms that produce a $(1+\epsilon)$-approximation in space $O(n/\epsilon^2)$ for every $\epsilon > 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. The prior state of the art ruled out $(2-\epsilon)$-approximation in $\tilde{O}(\sqrt{n})$ space or $(1+\epsilon)$-approximation in $n^{1-O(\epsilon)}$ space, for any $\epsilon > 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 $\epsilon$-close to forming a bipartite graph, using one-way communication.
The previous works proved a lower bound of $\Omega(\sqrt{n})$ for this task when $\epsilon=1/2$, and $n^{1-O(\epsilon)}$ for every $\epsilon>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 $\epsilon$-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(\epsilon)}$ communication protocol for this problem. In this work, we give an $\Omega(n)$ lower bound on the communication complexity of the original problem (without the extra information) for $\epsilon=\Omega(1)$ in the three-player setting.
Obtaining this $\Omega(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.
-
How to Fake Multiply by a Gaussian Matrix, ICML 2016M. Kapralov, V. Potluru and D. Woodruff
[Abstract]
Have you ever wanted to multiply an $n \times d$ matrix $X$, with $n \gg 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 \cdot X$ in only $O(\text{nnz}(X)) + \tilde O(m^2 \cdot d^{3})$ time, for which the total variation distance between the distributions $T \cdot X$ and $\tilde G \cdot X$ is as small as desired, i.e., less than any positive constant. Here $\text{nnz}(X)$ denotes the number of non-zero entries of $X$.
Assuming $\text{nnz}(X) \gg m^2 \cdot d^{3}$, this is a significant savings over the naive $O(\text{nnz}(X) m)$ time to compute $\tilde G \cdot X$. Moreover, since the total variation distance is small, we can provably use $T \cdot X$ in place of $\tilde G \cdot X$ in any application and have the same guarantees as if we were using $\tilde G \cdot X$, up to a small positive constant in error probability. We apply this transform to nonnegative matrix factorization (NMF) and support vector machines (SVM).
-
M. Kapralov
[Abstract]
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 the $\ell_2/\ell_2$ sparse recovery guarantees using Fourier measurements) using $O_d(k\log N\log\log N)$ samples of the signal in time domain that runs in time $O_d(k\log^{d+3} N)$, where $d\geq 1$ is the dimensionality of the Fourier transform.
The sample complexity matches the lower bound of $\Omega(k\log (N/k))$ for non-adaptive algorithms due to~\cite{DIPW} for any $k\leq N^{1-\delta}$ for a constant $\delta>0$ up to an $O(\log\log 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~\cite{IKP}, but for any dimension $d\geq 2$ previously known techniques either suffered from a $\text{poly}(\log N)$ factor loss in sample complexity or required $\Omega(N)$ runtime.
-
Subgraph Counting: Color Coding beyond Trees, IPDPS 2016V. T. Chakravarthy, M. Kapralov, P. Murali, F. Petrini, X. Que, Y. Sabharwal and B. Schieber
[Abstract]
The problem of counting occurrences of query graphs in a large data graph, known as subgraph counting, is fundamental to several domains such as genomics and social network analysis. Many important special cases (e.g. triangle counting) have received significant attention. Color coding is a very general and powerful algorithmic technique for subgraph counting.
Color coding has been shown to be effective in several applications, but scalable implementations are only known for the special case of tree queries (i.e. queries of treewidth one). In this paper we present the first efficient distributed implementation for color coding that goes beyond tree queries: our algorithm applies to any query graph of treewidth 2.
Since tree queries can be solved in time linear in the size of the data graph, our contribution is the first step into the realm of colour coding for queries that require superlinear running time in the worst case. This superlinear complexity leads to significant load balancing problems on graphs with heavy tailed degree distributions.
Our algorithm structures the computation to work around high degree nodes in the data graph, and achieves very good runtime and scalability on a diverse collection of data and query graph pairs as a result. We also provide theoretical analysis of our algorithmic techniques, showing asymptotic improvements in runtime on random graphs with power law degree distributions, a popular model for real world graphs.
-
M. Kapralov
[Abstract]
Locality Sensitive Hashing (LSH) has emerged as the method of choice for high dimensional similarity search, a classical problem of interest in numerous applications. LSH-based solutions require that each data point be inserted into a number $A$ of hash tables, after which a query can be answered by performing $B$ lookups. The original LSH solution of [IM98] showed for the first time that both $A$ and $B$ can be made sublinear in the number of data points.
Unfortunately, the classical LSH solution does not provide any tradeoff between insert and query complexity, whereas for data (respectively, query) intensive applications one would like to minimize insert time by choosing a smaller $A$ (respectively, minimize query time by choosing a smaller $B$).
A partial remedy for this is provided by Entropy LSH [Pan06], which allows to make either inserts or queries essentially constant time at the expense of a loss in the other parameter, but no algorithm that achieves a smooth tradeoff is known. In this paper, we present an algorithm for performing similarity search under the Euclidean metric that resolves the problem above.
Our solution is inspired by Entropy LSH, but uses a very different analysis to achieve a smooth tradeoff between insert and query complexity. Our results improve upon or match, up to lower order terms in the exponent, best known data-oblivious algorithms for the Euclidean metric.
-
M. Kapralov, S. Khanna and M. Sudan
[Abstract]
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 $\tilde{O}(n)$ space, then a near-optimal solution to the max cut value can be obtained by storing an $\tilde{O}(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 $\tilde{\Omega}(\sqrt{n})$ 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 $\frac{1}{2}$-far from being bipartite, and establishing that $\tilde{\Omega}(\sqrt{n})$ space is necessary to differentiate between these two cases.
Thus as a direct corollary we obtain that $\tilde{\Omega}(\sqrt{n})$ space is also necessary to test if a graph is bipartite or $\frac{1}{2}$-far from being bipartite. We also show that for any $\epsilon > 0$, any streaming algorithm that obtains a $(1 + \epsilon)$-approximation to the max cut value when edges arrive in adversarial order requires $n^{1 - O(\epsilon)}$ space, implying that $\Omega(n)$ space is necessary to obtain an arbitrarily good approximation to the max cut value.
-
Invited to the SICOMP special issue for FOCS 2014M. Kapralov, YT Lee, C. Musco, C. Musco and A. Sidford
[Abstract]
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 of $G$ into dimension $O(\frac{1}{\epsilon^2}n\text{poly}(\log n))$. Using this sketch, at any point, the algorithm can output a $(1 \pm \epsilon)$ spectral sparsifier for $G$ with high probability.
While $O(\frac{1}{\epsilon^2} n \text{poly}(\log n))$ space algorithms are known for computing cut sparsifiers in dynamic streams [AGM12b, GKP12] and spectral sparsifiers in insertion-only streams [KL11], prior to our work, the best known single pass algorithm for maintaining spectral sparsifiers in dynamic streams required sketches of dimension $\Omega(\frac{1}{\epsilon^2}n^{5/3})$ [AGM14].
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 $\ell_2/\ell_2$ sparse recovery, a natural extension of the $\ell_0$ methods used for cut sparsifiers in [AGM12b].
Recent work of [MP12] 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^\top A$ given a stream of updates to rows in $A$.
-
P. Indyk and M. Kapralov
[Abstract]
We give an algorithm for $\ell_2/\ell_2$ sparse recovery from Fourier measurements using $O(k\log N)$ samples, matching the lower bound of [DIPW] for non-adaptive algorithms up to constant factors for any $k\leq N^{1-\delta}$. The algorithm runs in $\tilde O(N)$ time. Our algorithm extends to higher dimensions, leading to sample complexity of $O_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.
-
Spanners and Sparsifiers in Dynamic Streams, PODC 2014Invited to the special issue for PODC 2014 in Distributed ComputingM. Kapralov and D. Woodruff
[Abstract]
Linear sketching is a popular technique for computing in dynamic streams, where one needs to handle both insertions and deletions of elements. The underlying idea of taking randomized linear measurements of input data has been extremely successful in providing space-efficient algorithms for classical problems such as frequency moment estimation and computing heavy hitters, and was very recently shown to be a powerful technique for solving graph problems in dynamic streams [AGM'12].
Ideally, one would like to obtain algorithms that use one or a small constant number of passes over the data and a small amount of space (i.e. sketching dimension) to preserve some useful properties of the input graph presented as a sequence of edge insertions and edge deletions.
In this paper, we concentrate on the problem of constructing linear sketches of graphs that (approximately) preserve the spectral information of the graph in a few passes over the stream. We do so by giving the first sketch-based algorithm for constructing multiplicative graph spanners in only two passes over the stream. Our spanners use $\tilde{O}(n^{1+1/k})$ bits of space and have stretch $2^k$.
While this stretch is larger than the conjectured optimal $2k-1$ for this amount of space, we show for an appropriate $k$ that it implies the first $2$-pass spectral sparsifier with $n^{1+o(1)}$ bits of space. Previous constructions of spectral sparsifiers in this model with a constant number of passes would require $n^{1+c}$ bits of space for a constant $c > 0$.
We also give an algorithm for constructing spanners that provides an additive approximation to the shortest path metric using a single pass over the data stream, also achieving an essentially best possible space/approximation tradeoff.
-
M. Kapralov, S. Khanna and M. Sudan
[Abstract]
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 $\tilde{O}(\sqrt{n})$ approximation with polylogarithmic space in an $n$ vertex graph and a constant approximation with $\Omega(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\cdot 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 = \Omega(\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.
-
P. Indyk, M. Kapralov and E. Price
[Abstract]
We consider the problem of computing a $k$-sparse approximation to the discrete Fourier transform of an $n$-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using $O(k \log n (\log\log n)^{O(1)})$ signal samples in time $O(k \log^2 n (\log\log n)^{O(1)})$, assuming that the entries of the signal are polynomially bounded.
The sampling complexity improves over the recent bound of $O(k \log n \log (n/k))$ given in [HIKP12], and matches the lower bound of $\Omega(k \log (n/k)/\log \log n)$ from the same paper up to $\mbox{poly}(\log \log n)$ factors when $k=O(n^{1-\delta})$ for a constant $\delta>0$.
-
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].
-
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.
-
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.
-
M. KapralovPh.D. thesis, Stanford University, August 2012Gene H. Golub Dissertation Award
[Abstract]
The problem of finding maximum matchings in bipartite graphs is a classical problem in combinatorial optimization with a long algorithmic history. Graph sparsification is a more recent paradigm of replacing a graph with a smaller subgraph that preserves some useful properties of the original graph, perhaps approximately. Traditionally, sparsification has been used for obtaining faster algorithms for cut-based optimization problems.
The contributions of this thesis are centered around new algorithms for bipartite matching problems, in which, surprisingly, graph sparsification plays a major role, and efficient algorithms for constructing sparsifiers in modern data models.
In the first part of the thesis we develop sublinear time algorithms for finding perfect matchings in regular bipartite graphs. These graphs have been studied extensively in the context of expander constructions, and have several applications in combinatorial optimization. The problem of finding perfect matchings in regular bipartite graphs has seen almost 100 years of algorithmic history, with the first algorithm dating back to König in 1916 and an algorithm with runtime linear in the number of edges in the graph discovered in 2000. In this thesis we show that, even though traditionally the use of sparsification has been restricted to cut-based problems, in fact sparsification yields extremely efficient sublinear time algorithms for finding perfect matchings in regular bipartite graphs when the graph is given in adjacency array representation. Thus, our algorithms recover a perfect matching (with high probability) without looking the whole input. We present two approaches, one based on independent sampling and another on random walks, obtaining an algorithm that recovers a perfect matching in O(n log n) time, within O(log n) of output complexity, essentially closing the problem.
In the second part of the thesis we study the streaming complexity of maximum bipartite matching. This problem is relevant to modern data models, where the algorithm is constrained in space and is only allowed few passes over the input. We are interested in determining the best tradeoff between the space usage and the quality of the solution obtained. We first study the problem in the single pass setting. A central object of our study is a new notion of sparsification relevant to matching problems: we define the notion of an $\epsilon$-matching cover of a bipartite graph as a subgraph that approximately preserves sizes of matchings between every two subsets of vertices, which can be viewed as a sparsifier for matching problems. We give an efficient construction of a sparse subgraph that we call a matching skeleton, which we show is a linear-size matching cover for a certain range of parameters (in fact, for $\epsilon > 1/2$). We then show that our sparsifier can be applied repeatedly while maintaining a non-trivial approximation ratio in the streaming model with vertex arrivals, obtaining the first 1 − 1/e deterministic one-pass streaming algorithm that uses linear space for this setting. Further, we show that this is in fact best possible: no algorithm can obtain a better than 1 − 1/e approximation in a single pass unless it uses significantly more than quasilinear space. This is a rather striking conclusion since a 1−1/e approximation can be obtained even in the more restrictive online model for this setting. Thus, we show that streaming algorithms can get no advantage over online algorithms for this problem unless they use substantially more than quasilinear space.
Our impossibility results for approximating matchings in a single pass using small space exploit a surprising connection between the sparsifiers that we define and a family of graphs known as Ruzsa–Szemerédi graphs. In particular, we show that bounding the best possible size of $\epsilon$-covers for general $\epsilon$ is essentially equivalent to determining the optimal size of an $\epsilon$-Ruzsa–Szemerédi graph. These graphs have received significant attention due to applications in PCP constructions, property testing and additive combinatorics, but determining their optimal size still remains a challenging open problem.
Besides giving matching upper and lower bounds for single pass algorithms in the vertex arrival setting, we also consider the problem of approximating matchings in multiple passes. Here we give an algorithm that achieves a factor of $1-e^{-k}k^k/k! = 1-1/\sqrt{2\pi k}+o(1/k)$ in $k$ passes, improving upon the previously best known approximation.
In the third part of the thesis we consider the concept of spectral sparsification introduced by Spielman and Teng. Here, we uncover a connection between spectral sparsification and spanners, i.e. subgraphs that approximately preserve shortest path distances. This connection allows us to obtain a quasilinear time algorithm for constructing spectral sparsifiers using approximate distance oracles and entirely bypassing linear system solvers, which was previously the only known way of constructing spectral sparsifiers in quasilinear time.
Finally, in the last part of the thesis we design an efficient implementation of cut-preserving sparsification in a streaming setting with edge deletions using only one pass over the data.
-
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.
-
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 2012M. 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.
-
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 2011M. 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.
-
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].
-
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, 2009A. Goel, M. Kapralov and S. Khanna
[Abstract]
A graph $G'(V,E')$ is an $\epsilon$-sparsification of $G$ for some $\epsilon>0$, if every (weighted) cut in $G'$ is within $(1\pm\epsilon)$ of the corresponding cut in $G$. A celebrated result of Benczúr and Karger shows that for every undirected graph $G$, an $\epsilon$-sparsification with $O(n\log n/\epsilon^2)$ edges can be constructed in $O(m\log^2 n)$ time. The notion of cut-preserving graph sparsification has played an important role in speeding up algorithms for several fundamental network design and routing problems. Applications to modern massive data sets often constrain algorithms to use computation models that restrict random access to the input. The semi-streaming model, in which the algorithm is constrained to use $\widetilde{O}(n)$ space, has been shown to be a good abstraction for analyzing graph algorithms in applications to large data sets. Recently, a semi-streaming algorithm for graph sparsification was presented by Anh and Guha; the total running time of their implementation is $\Omega(mn)$, too large for applications where both space and time are important. In this paper, we introduce a new technique for graph sparsification, namely refinement sampling, that gives an $\widetilde{O}(m)$ time semi-streaming algorithm for graph sparsification.
Specifically, we show that refinement sampling can be used to design a one-pass streaming algorithm for sparsification that takes $O(\log\log n)$ time per edge, uses $O(\log^2 n)$ space per node, and outputs an $\epsilon$-sparsifier with $O(n\log^3 n/\epsilon^2)$ edges. At a slightly increased space and time complexity, we can reduce the sparsifier size to $O(n\log n/\epsilon^2)$ edges matching the Benczúr-Karger result, while improving upon the Benczúr-Karger runtime for $m=\omega(n\log^3 n)$. Finally, we show that an $\epsilon$-sparsifier with $O(n\log n/\epsilon^2)$ edges can be constructed in two passes over the data and $O(m)$ time whenever $m=\Omega(n^{1+\delta})$ for some constant $\delta>0$. As a by-product of our approach, we also obtain an $O(m\log\log n+n\log n)$ time streaming algorithm to compute a sparse $k$-connectivity certificate of a graph.
-
Perfect matchings in Õ(n^{1.5}) time in regular bipartite graphs, 2009, to appear in CombinatoricaA. 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 2009Y. 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$).
Earlier 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
[Abstract]
We extend an efficient cone beam transform inversion formula, developed earlier by the authors for smooth curves with positive torsion, to a more general class of helix-like curves. These curves are allowed to have negative torsion, and they can be non-smooth at isolated points. The notions of turns and PI segments are extended. The new class is defined by several geometric conditions which impose a tradeoff between the length of critical PI lines (which reflect how severely the positivity of torsion is violated) and the extent to which the curve bends between neighboring turns. The main property of curves from this class is that critical PI lines are allowed to be arbitrarily close to the set U where reconstruction is possible, but are not allowed to intersect it. Some of the conditions that define the class turn out to be common for many known trajectories, so we investigate separately the properties of the Crofton symbol of PI segments of curves that satisfy these conditions. The results of the investigation are then used to develop an efficient filtered backprojection algorithm. Numerical experiments conducted with a clock phantom demonstrate good image quality.
-
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
[Abstract]
We report on two extensions of exact FBP inversion formulas to more general classes of trajectories. The first class consists of curves C that are smooth, have positive curvature and torsion, and have some other natural geometric properties. We generalize the notion of PI-lines, study their properties and formulate a 1PI FBP reconstruction algorithm. The second class of trajectories consists of circle-plus curves, which have two components: C and L. The first component C, which is analogous to the circle in the traditional circle-plus trajectories, is essentially any closed (not necessarily planar) continuous curve. The second component L is almost any continuous curve. The only condition is that L starts below C and ends above C. The algorithm is especially convenient for the traditional circle-plus trajectories, which are implemented using a gantry and moving table. In this case we obtain a universal FBP algorithm, which is completely independent of how the table moves during the scan. The results of testing both algorithms demonstrate good image quality.
-
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
[Abstract]
We extend an efficient cone beam transform inversion formula, proposed earlier by one of the authors for helices, to a general class of curves. The conditions that describe the class are very natural. Curves C are smooth, without self-intersections, have positive curvature and torsion, do not bend too much, and do not admit lines which are tangent to C at one point and intersect C at another point. The notions of PI-lines and PI-segments are generalized, their properties are studied. The domain U is found, where PI-lines are guaranteed to be unique. Results of numerical experiments demonstrate very good image quality.
-
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 articleM. Kapralov, A. Katsevich
[Abstract]
We develop an exact filtered backprojection reconstruction algorithm for dynamic-pitch helical trajectories when the convexity condition is violated. The algorithm is a modification of the original inversion formula, which was proposed earlier by one of the authors for a constant-pitch helix. Two filtering lines are added to the algorithm to guarantee exactness. We also study the region where the algorithm applies. It does not extend all the way to the helix, but its size depends on the severity of the violation. If the violation is not very strong, then the region is sufficiently large. Results of numerical experiments are presented.