2 citations · 4 across the 16 of their papers we have counts for
24 papers · 1 filter
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…
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 for Structured Graphs: 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,v…
Bi-Lipschitz extensions and outlier embeddings into trees
Shuchi Chawla, Arnold Filtser, Kristin Sheridan +1
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…
Stochastic Embedding of Digraphs into DAGs
Arnold Filtser
Given a weighted digraph , a stochastic embedding into DAGs is a distribution over pairs of DAGs such that for every : (1) the reachabilit…
How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
Jonathan Conroy, Arnold Filtser
Roughly, a metric space has padding parameter if for every , there is a stochastic decomposition of the metric points into clusters of diameter at most such that every…