Arnold Filtser

Lee-Ad Gottlieb

Discret. Comput. Geom., April, 2024

Online Spanners in Metric Spaces.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., March, 2024

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications.

[BibT_eX]

[DOI]

CoRR, 2024

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings.

[BibT_eX]

[DOI]

Sujoy Bhore

Csaba D. Tóth

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Static and Streaming Data Structures for Fréchet Distance Queries.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, October, 2023

Corrigendum: Metric Embedding via Shortest Path Decompositions.

[BibT_eX]

[DOI]

SIAM J. Comput., October, 2023

Approximate Nearest Neighbor for Curves: Simple, Efficient, and Deterministic.

[BibT_eX]

[DOI]

Matthew J. Katz

Algorithmica, May, 2023

Light, Reliable Spanners.

[BibT_eX]

[DOI]

Yuval Gitlitz

CoRR, 2023

Expander Decomposition in Dynamic Streams.

[BibT_eX]

[DOI]

Michael Kapralov

Mikhail Makarov

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Communication Complexity of Inner Product in Symmetric Normed Spaces.

[BibT_eX]

[DOI]

Alexandr Andoni

Jaroslaw Blasiok

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

Constructing light spanners deterministically in near-linear time.

[BibT_eX]

[DOI]

Christian Wulff-Nilsen

Theor. Comput. Sci., 2022

Metric Embedding via Shortest Path Decompositions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Light Spanners for High Dimensional Norms via Stochastic Decompositions.

[BibT_eX]

[DOI]

Algorithmica, 2022

Locality-sensitive orderings and applications to reliable spanners.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Low Treewidth Embeddings of Planar and Minor-Free Metrics.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Reliable Spanners: Locality-Sensitive Orderings Strike Back.

[BibT_eX]

[DOI]

CoRR, 2021

Clan embeddings into trees, and low treewidth graphs.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model.

[BibT_eX]

[DOI]

Michael Kapralov

Navid Nouri

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Hop-Constrained Metric Embeddings and their Applications.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Condorcet Relaxation In Spatial Voting.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

Ramsey Spanning Trees and Their Applications.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

The Greedy Spanner Is Existentially Optimal.

[BibT_eX]

[DOI]

Shay Solomon

SIAM J. Comput., 2020

Plurality in Spatial Voting Games with constant $β$.

[BibT_eX]

[DOI]

CoRR, 2020

Labelings vs. Embeddings: On Distributed Representations of Distances.

[BibT_eX]

[DOI]

Lee-Ad Gottlieb

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

A face cover perspective to ℓ1 embeddings of planar graphs.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Distributed Construction of Light Networks.

[BibT_eX]

[DOI]

Michael Elkin

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Scattering and Sparse Partitions, and Their Applications.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Steiner Point Removal with Distortion O(log k) using the Relaxed-Voronoi Algorithm.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

On notions of distortion and an almost minimum spanning tree with constant average distortion.

[BibT_eX]

[DOI]

Yair Bartal

J. Comput. Syst. Sci., 2019

A face cover perspective to 𝓁1 embeddings of planar graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Distributed monitoring of election winners.

[BibT_eX]

[DOI]

Nimrod Talmon

Artif. Intell., 2019

Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems.

[BibT_eX]

[DOI]

Ohad Trabelsi

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

On Strong Diameter Padded Decompositions.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Prioritized Metric Structures and Embedding.

[BibT_eX]

[DOI]

Michael Elkin

SIAM J. Comput., 2018

Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems.

[BibT_eX]

[DOI]

Ohad Trabelsi

CoRR, 2018

Steiner Point Removal with distortion O(log k), using the Noisy-Voronoi algorithm.

[BibT_eX]

[DOI]

CoRR, 2018

Steiner Point Removal with Distortion O(log k).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Terminal embeddings.

[BibT_eX]

[DOI]

Michael Elkin

Theor. Comput. Sci., 2017

Sparsification of Two-Variable Valued Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Steiner Point Removal with Distortion O(log k).

[BibT_eX]

[DOI]

CoRR, 2017

2015

Sparsification of Two-Variable Valued CSPs.

[BibT_eX]

[DOI]