
APMF < APSP? GomoryHu Tree for Unweighted Graphs in AlmostQuadratic Time
We design an n^2+o(1)time algorithm that constructs a cutequivalent (G...
read it

Spectral Hypergraph Sparsifiers of Nearly Linear Size
Graph sparsification has been studied extensively over the past two deca...
read it

Smoothness of Schatten Norms and SlidingWindow Matrix Streams
Large matrices are often accessed as a roworder stream. We consider the...
read it

Sparse Normal Means Estimation with Sublinear Communication
We consider the problem of sparse normal means estimation in a distribut...
read it

Subcubic Algorithms for GomoryHu Tree in Unweighted Graphs
Every undirected graph G has a (weighted) cutequivalent tree T, commonl...
read it

Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Cut and spectral sparsification of graphs have numerous applications, in...
read it

Streaming Algorithms for Geometric Steiner Forest
We consider a natural generalization of the Steiner tree problem, the St...
read it

NearOptimal Entrywise Sampling of Numerically Sparse Matrices
Many realworld data sets are sparse or almost sparse. One method to mea...
read it

Approximating the Median under the Ulam Metric
We study approximation algorithms for variants of the median string prob...
read it

CutEquivalent Trees are Optimal for MinCut Queries
MinCut queries are fundamental: Preprocess an undirected edgeweighted ...
read it

Coresets for Clustering in Excludedminor Graphs and Beyond
Coresets are modern datareduction tools that are widely used in data an...
read it

Faster Algorithms for Orienteering and kTSP
We consider the rooted orienteering problem in Euclidean space: Given n ...
read it

Sublinear Algorithms for Gap Edit Distance
The edit distance is a way of quantifying how similar two strings are to...
read it

Labelings vs. Embeddings: On Distributed Representations of Distances
We investigate for which metric spaces the performance of distance label...
read it

Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
The spectrum of a matrix contains important structural information about...
read it

Coresets for Clustering in Graphs of Bounded Treewidth
We initiate the study of coresets for clustering in graph metrics, i.e.,...
read it

Tight Recovery Guarantees for Orthogonal Matching Pursuit Under Gaussian Noise
Orthogonal Matching pursuit (OMP) is a popular algorithm to estimate an ...
read it

AlmostSmooth Histograms and SlidingWindow Graph Algorithms
We study algorithms for the slidingwindow model, an important variant o...
read it

Coresets for Ordered Weighted Clustering
We design coresets for Ordered kMedian, a generalization of classical c...
read it

New Algorithms and Lower Bounds for AllPairs MaxFlow in Undirected Graphs
We investigate the timecomplexity of the AllPairs MaxFlow problem: Gi...
read it

Universal Streaming of Subset Norms
Most known algorithms in the streaming model of computation aim to appro...
read it

FlowCut Gaps and Face Covers in Planar Graphs
The relationship between the sparsest cut and the maximum concurrent mul...
read it

On Solving Linear Systems in Sublinear Time
We study sublinear algorithms that solve linear systems locally. In the ...
read it

Relaxed Voronoi: a Simple Framework for TerminalClustering Problems
We reprove three known algorithmic bounds for terminalclustering proble...
read it

Noisy Voronoi: a Simple Framework for TerminalClustering Problems
We reprove three known (algorithmic) bounds for terminalclustering prob...
read it

Batch Sparse Recovery, or How to Leverage the Average Sparsity
We introduce a batch version of sparse recovery, where the goal is to re...
read it

Faster Algorithms for AllPairs Bounded MinCuts
Given a directed graph, the vertex connectivity from u to v is the maxim...
read it

Revisiting the Set Cover Conjecture
In the Set Cover problem, the input is a ground set of n elements and a ...
read it

Do semidefinite relaxations solve sparse PCA up to the information limit?
Estimating the leading principal components of data, assuming they are s...
read it

Efficient Classification for Metric Data
Recent advances in largemargin classification of data residing in gener...
read it

Adaptive Metric Dimensionality Reduction
We study adaptive datadependent dimensionality reduction in the context...
read it
Robert Krauthgamer
is this you? claim profile