
HopConstrained Metric Embeddings and their Applications
In network design problems, such as compact routing, the goal is to rout...
read it

Reliable Spanners: LocalitySensitive Orderings Strike Back
Chan, HarPeled, and Jones [2020] recently developed localitysensitive ...
read it

Clan Embeddings into Trees, and Low Treewidth Graphs
In low distortion metric embeddings, the goal is to embed a host "hard" ...
read it

On Light Spanners, Lowtreewidth Embeddings and Efficient Traversing in Minorfree Graphs
Understanding the structure of minorfree metrics, namely shortest path ...
read it

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
Graph sketching is a powerful technique introduced by the seminal work o...
read it

Static and Streaming Data Structures for Fréchet Distance Queries
Given a curve P with points in ℝ^d in a streaming fashion, and parameter...
read it

Plurality in Spatial Voting Games with constant β
Consider a set of voters V, represented by a multiset in a metric space ...
read it

Scattering and Sparse Partitions, and their Applications
A partition P of a weighted graph G is (σ,τ,Δ)sparse if every cluster h...
read it

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

On Strong Diameter Padded Decompositions
Given a weighted graph G=(V,E,w), a partition of V is Δbounded if the d...
read it

Distributed Construction of Light Networks
A t spanner H of a weighted graph G=(V,E,w) is a subgraph that approxim...
read it

A face cover perspective to ℓ_1 embeddings of planar graphs
It was conjectured by Gupta et. al. [Combinatorica04] that every planar ...
read it

Approximate Nearest Neighbor for Curves  Simple, Efficient, and Deterministic
In the (1+ε,r)approximatenearneighbor problem for curves (ANNC) under...
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

Steiner Point Removal with distortion O( k), using the NoisyVoronoi algorithm
In the Steiner Point Removal (SPR) problem, we are given a weighted grap...
read it

Distributed Monitoring of Election Winners
We consider distributed elections, where there is a center and k sites. ...
read it

Light Spanners for High Dimensional Norms via Stochastic Decompositions
Spanners for low dimensional spaces (e.g. Euclidean space of constant di...
read it
Arnold Filtser
is this you? claim profile