research
∙
08/02/2023
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
A spanning tree T of graph G is a ρ-approximate universal Steiner tree (...
share
research
∙
07/31/2023
Light, Reliable Spanners
A ν-reliable spanner of a metric space (X,d), is a (dominating) graph H,...
research
∙
11/24/2022
Communication Complexity of Inner Product in Symmetric Normed Spaces
We introduce and study the communication complexity of computing the inn...
research
∙
11/21/2022
Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings
Chan, Har-Peled, and Jones [SICOMP 2020] developed locality-sensitive or...
research
∙
11/21/2022
Expander Decomposition in Dynamic Streams
In this paper we initiate the study of expander decompositions of a grap...
research
∙
03/29/2022
Low Treewidth Embeddings of Planar and Minor-Free Metrics
Cohen-Addad, Filtser, Klein and Le [FOCS'20] constructed a stochastic em...
research
∙
02/21/2022
Online Spanners in Metric Spaces
Given a metric space ℳ=(X,δ), a weighted graph G over X is a metric t-sp...
research
∙
06/28/2021
Hop-Constrained Metric Embeddings and their Applications
In network design problems, such as compact routing, the goal is to rout...
research
∙
01/19/2021
Reliable Spanners: Locality-Sensitive Orderings Strike Back
Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ...
research
∙
01/04/2021
Clan Embeddings into Trees, and Low Treewidth Graphs
In low distortion metric embeddings, the goal is to embed a host "hard" ...
research
∙
09/10/2020
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
Understanding the structure of minor-free metrics, namely shortest path ...
research
∙
07/28/2020
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
Graph sketching is a powerful technique introduced by the seminal work o...
research
∙
07/21/2020
Static and Streaming Data Structures for Fréchet Distance Queries
Given a curve P with points in ℝ^d in a streaming fashion, and parameter...
research
∙
05/10/2020
Plurality in Spatial Voting Games with constant β
Consider a set of voters V, represented by a multiset in a metric space ...
research
∙
01/13/2020
Scattering and Sparse Partitions, and their Applications
A partition P of a weighted graph G is (σ,τ,Δ)-sparse if every cluster h...
research
∙
07/16/2019
Labelings vs. Embeddings: On Distributed Representations of Distances
We investigate for which metric spaces the performance of distance label...
research
∙
06/24/2019
On Strong Diameter Padded Decompositions
Given a weighted graph G=(V,E,w), a partition of V is Δ-bounded if the d...
research
∙
05/07/2019
Distributed Construction of Light Networks
A t- spanner H of a weighted graph G=(V,E,w) is a subgraph that approxim...
research
∙
03/07/2019
A face cover perspective to ℓ_1 embeddings of planar graphs
It was conjectured by Gupta et. al. [Combinatorica04] that every planar ...
research
∙
02/20/2019
Approximate Nearest Neighbor for Curves --- Simple, Efficient, and Deterministic
In the (1+ε,r)-approximate-near-neighbor problem for curves (ANNC) under...
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
∙
08/08/2018
Steiner Point Removal with distortion O( k), using the Noisy-Voronoi algorithm
In the Steiner Point Removal (SPR) problem, we are given a weighted grap...
research
∙
05/06/2018
Distributed Monitoring of Election Winners
We consider distributed elections, where there is a center and k sites. ...
research
∙
04/20/2018