Arnold Filtser | DeepAI

AI Chat

Featured Co-authors

Hung Le
76 publications
Robert Krauthgamer
51 publications
Vincent Cohen-Addad
45 publications
Nimrod Talmon
43 publications
Csaba D. Tóth
36 publications
Michael Kapralov
30 publications
Sujoy Bhore
29 publications
D. Ellis Hershkowitz
17 publications
Jarosław Błasiok
17 publications
Alexandr Andoni
15 publications
Michael Elkin
15 publications

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

0 Costas Busch, et al. ∙

∙ 07/31/2023

Light, Reliable Spanners

A ν-reliable spanner of a metric space (X,d), is a (dominating) graph H,...

0 Arnold Filtser, et al. ∙

∙ 11/24/2022

Communication Complexity of Inner Product in Symmetric Normed Spaces

We introduce and study the communication complexity of computing the inn...

0 Alexandr Andoni, et al. ∙

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

0 Arnold Filtser, et al. ∙

∙ 11/21/2022

Expander Decomposition in Dynamic Streams

In this paper we initiate the study of expander decompositions of a grap...

0 Arnold Filtser, et al. ∙

∙ 03/29/2022

Low Treewidth Embeddings of Planar and Minor-Free Metrics

Cohen-Addad, Filtser, Klein and Le [FOCS'20] constructed a stochastic em...

0 Arnold Filtser, et al. ∙

∙ 02/21/2022

Online Spanners in Metric Spaces

Given a metric space ℳ=(X,δ), a weighted graph G over X is a metric t-sp...

0 Sujoy Bhore, et al. ∙

∙ 06/28/2021

Hop-Constrained Metric Embeddings and their Applications

In network design problems, such as compact routing, the goal is to rout...

0 Arnold Filtser, et al. ∙

∙ 01/19/2021

Reliable Spanners: Locality-Sensitive Orderings Strike Back

Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ...

0 Arnold Filtser, et al. ∙

∙ 01/04/2021

Clan Embeddings into Trees, and Low Treewidth Graphs

In low distortion metric embeddings, the goal is to embed a host "hard" ...

0 Arnold Filtser, et al. ∙

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

0 Vincent Cohen-Addad, et al. ∙

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

0 Arnold Filtser, et al. ∙

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

0 Arnold Filtser, et al. ∙

∙ 05/10/2020

Plurality in Spatial Voting Games with constant β

Consider a set of voters V, represented by a multiset in a metric space ...

0 Arnold Filtser, et al. ∙

∙ 01/13/2020

Scattering and Sparse Partitions, and their Applications

A partition P of a weighted graph G is (σ,τ,Δ)-sparse if every cluster h...

0 Arnold Filtser, et al. ∙

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

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

0 Arnold Filtser, et al. ∙

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

0 Michael Elkin, et al. ∙

∙ 03/07/2019

A face cover perspective to ℓ_1 embeddings of planar graphs

It was conjectured by Gupta et. al. [Combinatorica04] that every planar ...

0 Arnold Filtser, et al. ∙

∙ 02/20/2019

Approximate Nearest Neighbor for Curves --- Simple, Efficient, and Deterministic

In the (1+ε,r)-approximate-near-neighbor problem for curves (ANNC) under...

0 Arnold Filtser, et al. ∙

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

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

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

0 Arnold Filtser, et al. ∙

∙ 05/06/2018

Distributed Monitoring of Election Winners

We consider distributed elections, where there is a center and k sites. ...

0 Arnold Filtser, et al. ∙

∙ 04/20/2018

Light Spanners for High Dimensional Norms via Stochastic Decompositions

Spanners for low dimensional spaces (e.g. Euclidean space of constant di...

0 Arnold Filtser, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world