Ofer Neiman

Richard Spence

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2024

Path-Reporting Distance Oracles with Linear Size.

[BibT_eX]

[DOI]

Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

On the Size Overhead of Pairwise Spanners.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Light, Reliable Spanners.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

Corrigendum: Metric Embedding via Shortest Path Decompositions.

[BibT_eX]

[DOI]

SIAM J. Comput., October, 2023

2022

Distributed strong diameter network decomposition.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Almost Shortest Paths with Near-Additive Error in Weighted Graphs.

[BibT_eX]

[DOI]

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

A Unified Framework for Hopsets.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

A Unified Framework for Hopsets and Spanners.

[BibT_eX]

[DOI]

CoRR, 2021

Improved Weighted Additive Spanners.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Distributed Computing, 2021

2020

Near-Additive Spanners and Near-Exact Hopsets, A Unified View.

[BibT_eX]

[DOI]

Bull. EATCS, 2020

Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication.

[BibT_eX]

[DOI]

CoRR, 2020

Lossless Prioritized Embeddings.

[BibT_eX]

[DOI]

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

Distributed Construction of Light Networks.

[BibT_eX]

[DOI]

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

2019

Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC.

[BibT_eX]

[DOI]

Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

Dimensionality reduction: theoretical perspective on practical measures.

[BibT_eX]

[DOI]

Nova Fandina

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Covering Metric Spaces by Few Trees.

[BibT_eX]

[DOI]

Nova Fandina

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

On efficient distributed construction of near optimal routing schemes.

[BibT_eX]

[DOI]

Distributed Comput., 2018

Metric embedding via shortest path decompositions.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Ramsey Spanning Trees and their Applications.

[BibT_eX]

[DOI]

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

Near-Optimal Distributed Routing with Low Memory.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Light Spanners for High Dimensional Norms via Stochastic Decompositions.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Near Isometric Terminal Embeddings for Doubling Metrics.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory.

[BibT_eX]

[DOI]

CoRR, 2017

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Spanning Trees with Low Average Stretch.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Space-efficient path-reporting approximate distance oracles.

[BibT_eX]

[DOI]

Christian Wulff-Nilsen

Theor. Comput. Sci., 2016

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Distributed Strong Diameter Network Decomposition: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost.

[BibT_eX]

[DOI]

Alexandr Andoni

Assaf Naor

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ<sub>p</sub>.

[BibT_eX]

[DOI]

Lee-Ad Gottlieb

SIAM J. Discret. Math., 2015

On vertex rankings of graphs and its relatives.

[BibT_eX]

[DOI]

Ilan Karpas

Shakhar Smorodinsky

Discret. Math., 2015

Prioritized Metric Structures and Embedding.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Terminal Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Light Spanners.

[BibT_eX]

[DOI]

Shay Solomon

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp.

[BibT_eX]

[DOI]

Lee-Ad Gottlieb

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ<sub>p</sub>, p>2.

[BibT_eX]

[DOI]

Lee-Ad Gottlieb

CoRR, 2013

Low Dimensional Embeddings of Doubling Metrics.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 2013

Simple deterministic algorithms for fully dynamic maximal matching.

[BibT_eX]

[DOI]

Shay Solomon

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Deterministic Algorithms for Fully Dynamic Maximal Matching

[BibT_eX]

[DOI]

Shay Solomon

CoRR, 2012

Using petal-decompositions to build a low stretch spanning tree.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Beck's Three Permutations Conjecture: A Counterexample and Some Consequences.

[BibT_eX]

[DOI]

Alantha Newman

Aleksandar Nikolov

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Dynamic Inefficiency: Anarchy without Stability.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory, 4th International Symposium, 2011

Near Linear Lower Bound for Dimension Reduction in L1.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Bandwidth and Low Dimensional Embedding.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Volume in General Metric Spaces.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

2009

A novel approach to embedding of metric spaces (גישה חדשה לשיכונים של מרחבים מטריים.).

[BibT_eX]

[DOI]

PhD thesis, 2009

On low dimensional local embeddings.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Embedding metric spaces in their intrinsic dimension.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Nearly Tight Low Stretch Spanning Trees.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Local embeddings of metric spaces.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Advances in metric embedding theory.

[BibT_eX]

[DOI]