research
∙
07/18/2023
Cut Sparsification and Succinct Representation of Submodular Hypergraphs
In cut sparsification, all cuts of a hypergraph H=(V,E,w) are approximat...
share
research
∙
07/15/2023
Fully Scalable MPC Algorithms for Clustering in High Dimension
We design new algorithms for k-clustering in high-dimensional Euclidean ...
research
∙
03/28/2023
Lower Bounds for Pseudo-Deterministic Counting in a Stream
Many streaming algorithms provide only a high-probability relative appro...
research
∙
12/04/2022
Clustering Permutations: New Techniques with Streaming Applications
We study the classical metric k-median clustering problem over a set of ...
research
∙
11/22/2022
An Algorithmic Bridge Between Hamming and Levenshtein Distances
The edit distance between strings classically assigns unit cost to every...
research
∙
11/10/2022
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Max-Cut is a fundamental problem that has been studied extensively in va...
research
∙
09/15/2022
Distributed Sparse Linear Regression with Sublinear Communication
We study the problem of high-dimensional sparse linear regression in a d...
research
∙
09/05/2022
The Power of Uniform Sampling for Coresets
Motivated by practical generalizations of the classic k-median and k-mea...
research
∙
07/15/2022
Exact Flow Sparsification Requires Unbounded Size
Given a large edge-capacitated network G and a subset of k vertices call...
research
∙
07/04/2022
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs
In vertex-cut sparsification, given a graph G=(V,E) with a terminal set ...
research
∙
06/21/2022
Near-Linear ε-Emulators for Planar Graphs
We study vertex sparsification for distances, in the setting of planar g...
research
∙
04/05/2022
Streaming Facility Location in High Dimension via New Geometric Hashing
In Euclidean Uniform Facility Location, the input is a set of clients in...
research
∙
01/30/2022
Comparison of Matrix Norm Sparsification
Matrix sparsification is a well-known approach in the design of efficien...
research
∙
12/10/2021
Flow Metrics on Graphs
Given a graph with non-negative edge weights, there are various ways to ...
research
∙
11/24/2021
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
We study the problem of approximating edit distance in sublinear time. T...
research
∙
11/09/2021
Gomory-Hu Tree in Subcubic Time
In 1961, Gomory and Hu showed that the max-flow values of all n 2 pairs ...
research
∙
10/29/2021
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
We devise new cut sparsifiers that are related to the classical sparsifi...
research
∙
10/06/2021
Coresets for Kernel Clustering
We devise the first coreset for kernel k-Means, and use it to obtain new...
research
∙
07/20/2021
Approximate Trace Reconstruction via Median String (in Average-Case)
We consider an approximate version of the trace reconstruction problem, ...
research
∙
06/30/2021
Coresets for Clustering with Missing Values
We provide the first coreset for clustering points in ℝ^d that have mult...
research
∙
06/05/2021
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
We design an n^2+o(1)-time algorithm that constructs a cut-equivalent (G...
research
∙
06/04/2021
Spectral Hypergraph Sparsifiers of Nearly Linear Size
Graph sparsification has been studied extensively over the past two deca...
research
∙
03/15/2021
Smoothness of Schatten Norms and Sliding-Window Matrix Streams
Large matrices are often accessed as a row-order stream. We consider the...
research
∙
02/05/2021
Sparse Normal Means Estimation with Sublinear Communication
We consider the problem of sparse normal means estimation in a distribut...
research
∙
12/18/2020
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
Every undirected graph G has a (weighted) cut-equivalent tree T, commonl...
research
∙
11/12/2020
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Cut and spectral sparsification of graphs have numerous applications, in...
research
∙
11/09/2020
Streaming Algorithms for Geometric Steiner Forest
We consider a natural generalization of the Steiner tree problem, the St...
research
∙
11/03/2020
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
Many real-world data sets are sparse or almost sparse. One method to mea...
research
∙
11/02/2020
Approximating the Median under the Ulam Metric
We study approximation algorithms for variants of the median string prob...
research
∙
09/13/2020
Cut-Equivalent Trees are Optimal for Min-Cut Queries
Min-Cut queries are fundamental: Preprocess an undirected edge-weighted ...
research
∙
04/16/2020
Coresets for Clustering in Excluded-minor Graphs and Beyond
Coresets are modern data-reduction tools that are widely used in data an...
research
∙
02/18/2020
Faster Algorithms for Orienteering and k-TSP
We consider the rooted orienteering problem in Euclidean space: Given n ...
research
∙
10/02/2019
Sublinear Algorithms for Gap Edit Distance
The edit distance is a way of quantifying how similar two strings are to...
research
∙
07/16/2019
Labelings vs. Embeddings: On Distributed Representations of Distances
We investigate for which metric spaces the performance of distance label...
research
∙
07/11/2019
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
The spectrum of a matrix contains important structural information about...
research
∙
07/10/2019
Coresets for Clustering in Graphs of Bounded Treewidth
We initiate the study of coresets for clustering in graph metrics, i.e.,...
research
∙
05/29/2019
Tight Recovery Guarantees for Orthogonal Matching Pursuit Under Gaussian Noise
Orthogonal Matching pursuit (OMP) is a popular algorithm to estimate an ...
research
∙
04/16/2019
Almost-Smooth Histograms and Sliding-Window Graph Algorithms
We study algorithms for the sliding-window model, an important variant o...
research
∙
03/11/2019
Coresets for Ordered Weighted Clustering
We design coresets for Ordered k-Median, a generalization of classical c...
research
∙
01/05/2019
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
We investigate the time-complexity of the All-Pairs Max-Flow problem: Gi...
research
∙
12/01/2018
Universal Streaming of Subset Norms
Most known algorithms in the streaming model of computation aim to appro...
research
∙
11/06/2018
Flow-Cut Gaps and Face Covers in Planar Graphs
The relationship between the sparsest cut and the maximum concurrent mul...
research
∙
09/09/2018
On Solving Linear Systems in Sublinear Time
We study sublinear algorithms that solve linear systems locally. In the ...
research
∙
09/04/2018
Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
We reprove three known algorithmic bounds for terminal-clustering proble...
research
∙
09/04/2018
Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems
We reprove three known (algorithmic) bounds for terminal-clustering prob...
research
∙
07/23/2018
Batch Sparse Recovery, or How to Leverage the Average Sparsity
We introduce a batch version of sparse recovery, where the goal is to re...
research
∙
07/16/2018
Faster Algorithms for All-Pairs Bounded Min-Cuts
Given a directed graph, the vertex connectivity from u to v is the maxim...
research
∙
11/21/2017
Revisiting the Set Cover Conjecture
In the Set Cover problem, the input is a ground set of n elements and a ...
research
∙
06/16/2013
Do semidefinite relaxations solve sparse PCA up to the information limit?
Estimating the leading principal components of data, assuming they are s...
research
∙
06/11/2013