14 papers
Fatness and Flatness
Arnold Filtser, Hung Le, Nikolas Mählmann +2
Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of s…
Hop-Constrained Metric Embeddings and their Applications
Arnold Filtser
In network design problems, such as compact routing, the goal is to route packets between nodes using the (approximated) shortest paths. A desirable property of these routes is a s…
Directed Low Diameter Decomposition for Structured Digraphs
Shinwoo An, Arnold Filtser
Low diameter decompositions, or LDDs for short, are a fundamental primitive in the design of efficient graph algorithms. Roughly speaking, an LDD is a distribution over partitions…
Bi-Lipschitz extensions and outlier embeddings into trees
Shuchi Chawla, Arnold Filtser, Yoni Trachtenberg +2
We develop low distortion embeddings with outliers from arbitrary metrics into hierarchically separated trees (HSTs). In particular, we develop an efficient algorithm that for any…
Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
Arnold Filtser, Orr Fischer
In the -Proof Labeling Scheme model (-PLS model), our goal is to certify that a network of nodes satisfies a given property . A prover assigns a label to each node, and ea…
DAG Covers: The Steiner Point Effect
Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4
Given a weighted digraph , a -DAG cover is a collection of dominating DAGs such that all distances are approximately preserved: for every pair $(u,…