Robert Krauthgamer

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...

0 Yotam Kenneth, et al. ∙

research

∙ 07/15/2023

Fully Scalable MPC Algorithms for Clustering in High Dimension

We design new algorithms for k-clustering in high-dimensional Euclidean ...

0 Artur Czumaj, et al. ∙

research

∙ 03/28/2023

Lower Bounds for Pseudo-Deterministic Counting in a Stream

Many streaming algorithms provide only a high-probability relative appro...

0 Vladimir Braverman, et al. ∙

research

∙ 12/04/2022

Clustering Permutations: New Techniques with Streaming Applications

We study the classical metric k-median clustering problem over a set of ...

0 Diptarka Chakraborty, et al. ∙

research

∙ 11/22/2022

An Algorithmic Bridge Between Hamming and Levenshtein Distances

The edit distance between strings classically assigns unit cost to every...

0 Elazar Goldenberg, et al. ∙

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...

0 Yu Chen, et al. ∙

research

∙ 09/15/2022

Distributed Sparse Linear Regression with Sublinear Communication

We study the problem of high-dimensional sparse linear regression in a d...

0 Chen Amiraz, et al. ∙

research

∙ 09/05/2022

The Power of Uniform Sampling for Coresets

Motivated by practical generalizations of the classic k-median and k-mea...

0 Vladimir Braverman, et al. ∙

research

∙ 07/15/2022

Exact Flow Sparsification Requires Unbounded Size

Given a large edge-capacitated network G and a subset of k vertices call...

0 Robert Krauthgamer, et al. ∙

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 ...

0 Itai Boneh, et al. ∙

research

∙ 06/21/2022

Near-Linear ε-Emulators for Planar Graphs

We study vertex sparsification for distances, in the setting of planar g...

0 Hsien-Chih Chang, et al. ∙

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...

0 Artur Czumaj, et al. ∙

research

∙ 01/30/2022

Comparison of Matrix Norm Sparsification

Matrix sparsification is a well-known approach in the design of efficien...

0 Robert Krauthgamer, et al. ∙

research

∙ 12/10/2021

Flow Metrics on Graphs

Given a graph with non-negative edge weights, there are various ways to ...

0 Lior Kalman, et al. ∙

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...

0 Elazar Goldenberg, et al. ∙

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 ...

0 Amir Abboud, et al. ∙

research

∙ 10/29/2021

Friendly Cut Sparsifiers and Faster Gomory-Hu Trees

We devise new cut sparsifiers that are related to the classical sparsifi...

0 Amir Abboud, et al. ∙

research

∙ 10/06/2021

Coresets for Kernel Clustering

We devise the first coreset for kernel k-Means, and use it to obtain new...

0 Shaofeng H. -C. Jiang, et al. ∙

research

∙ 07/20/2021

Approximate Trace Reconstruction via Median String (in Average-Case)

We consider an approximate version of the trace reconstruction problem, ...

0 Diptarka Chakraborty, et al. ∙

research

∙ 06/30/2021

Coresets for Clustering with Missing Values

We provide the first coreset for clustering points in ℝ^d that have mult...

0 Vladimir Braverman, et al. ∙

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...

0 Amir Abboud, et al. ∙

research

∙ 06/04/2021

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Graph sparsification has been studied extensively over the past two deca...

0 Michael Kapralov, et al. ∙

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...

0 Robert Krauthgamer, et al. ∙

research

∙ 02/05/2021

Sparse Normal Means Estimation with Sublinear Communication

We consider the problem of sparse normal means estimation in a distribut...

0 Chen Amiraz, et al. ∙

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...

0 Amir Abboud, et al. ∙

research

∙ 11/12/2020

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Cut and spectral sparsification of graphs have numerous applications, in...

0 Michael Kapralov, et al. ∙

research

∙ 11/09/2020

Streaming Algorithms for Geometric Steiner Forest

We consider a natural generalization of the Steiner tree problem, the St...

0 Artur Czumaj, et al. ∙

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...

0 Vladimir Braverman, et al. ∙

research

∙ 11/02/2020

Approximating the Median under the Ulam Metric

We study approximation algorithms for variants of the median string prob...

0 Diptarka Chakraborty, et al. ∙

research

∙ 09/13/2020

Cut-Equivalent Trees are Optimal for Min-Cut Queries

Min-Cut queries are fundamental: Preprocess an undirected edge-weighted ...

0 Amir Abboud, et al. ∙

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...

0 Vladimir Braverman, et al. ∙

research

∙ 02/18/2020

Faster Algorithms for Orienteering and k-TSP

We consider the rooted orienteering problem in Euclidean space: Given n ...

0 Lee-Ad Gottlieb, et al. ∙

research

∙ 10/02/2019

Sublinear Algorithms for Gap Edit Distance

The edit distance is a way of quantifying how similar two strings are to...

0 Elazar Goldenberg, et al. ∙

research

∙ 07/16/2019

Labelings vs. Embeddings: On Distributed Representations of Distances

We investigate for which metric spaces the performance of distance label...

0 Arnold Filtser, et al. ∙

research

∙ 07/11/2019

Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension

The spectrum of a matrix contains important structural information about...

0 Vladimir Braverman, et al. ∙

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.,...

0 Vladimir Braverman, et al. ∙

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 ...

0 Chen Amiraz, et al. ∙

research

∙ 04/16/2019

Almost-Smooth Histograms and Sliding-Window Graph Algorithms

We study algorithms for the sliding-window model, an important variant o...

0 Robert Krauthgamer, et al. ∙

research

∙ 03/11/2019

Coresets for Ordered Weighted Clustering

We design coresets for Ordered k-Median, a generalization of classical c...

0 Vladimir Braverman, et al. ∙

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...

0 Amir Abboud, et al. ∙

research

∙ 12/01/2018

Universal Streaming of Subset Norms

Most known algorithms in the streaming model of computation aim to appro...

0 Vladimir Braverman, et al. ∙

research

∙ 11/06/2018

Flow-Cut Gaps and Face Covers in Planar Graphs

The relationship between the sparsest cut and the maximum concurrent mul...

0 Robert Krauthgamer, et al. ∙

research

∙ 09/09/2018

On Solving Linear Systems in Sublinear Time

We study sublinear algorithms that solve linear systems locally. In the ...

0 Alexandr Andoni, et al. ∙

research

∙ 09/04/2018

Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems

We reprove three known algorithmic bounds for terminal-clustering proble...

0 Arnold Filtser, et al. ∙

research

∙ 09/04/2018

Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems

We reprove three known (algorithmic) bounds for terminal-clustering prob...

0 Arnold Filtser, et al. ∙

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...

0 Alexandr Andoni, et al. ∙

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...

0 Amir Abboud, et al. ∙

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 ...

0 Robert Krauthgamer, et al. ∙

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...

0 Robert Krauthgamer, et al. ∙

research

∙ 06/11/2013

Efficient Classification for Metric Data

Recent advances in large-margin classification of data residing in gener...

0 Lee-Ad Gottlieb, et al. ∙

Robert Krauthgamer

Featured Co-authors