O. Neiman

Most-cited papers

Simple deterministic algorithms for fully dynamic maximal matching
O. Neiman, Shay Solomon
2012Symposium on the Theory of Computing144 citations
Semantic Scholar
Using petal-decompositions to build a low stretch spanning tree
Ittai Abraham, O. Neiman
2012Symposium on the Theory of Computing131 citations Open access
Semantic Scholar
Nearly Tight Low Stretch Spanning Trees
Ittai Abraham, Y. Bartal, O. Neiman
20082008 49th Annual IEEE Symposium on Foundations of Computer Science120 citations Open access
Semantic Scholar
Metric embeddings with relaxed guarantees
Ittai Abraham, Y. Bartal, T.-H. Hubert Chan, Kedar Dhamdhere +4 more
2005IEEE Annual Symposium on Foundations of Computer Science105 citations Open access
Semantic Scholar
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
Michael Elkin, O. Neiman
2016ACM-SIAM Symposium on Discrete Algorithms91 citations Open access
Semantic Scholar
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
Michael Elkin, O. Neiman
2016IEEE Annual Symposium on Foundations of Computer Science90 citations Open access
Semantic Scholar
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
Ittai Abraham, C. Gavoille, Anupam Gupta, O. Neiman +1 more
2013Symposium on the Theory of Computing78 citations
Semantic Scholar
Assouad's theorem with dimension independent of the snowflaking
A. Naor, O. Neiman
201059 citations Open access
Semantic Scholar
Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
Ittai Abraham, Y. Bartal, O. Neiman
2006ACM-SIAM Symposium on Discrete Algorithms46 citations Open access
Semantic Scholar
Terminal embeddings
Michael Elkin, Arnold Filtser, O. Neiman
2016Theoretical Computer Science45 citations Open access
Semantic Scholar
Snowflake universality of Wasserstein spaces
Alexandr Andoni, A. Naor, O. Neiman
201544 citations Open access
Semantic Scholar
Embedding metric spaces in their intrinsic dimension
Ittai Abraham, Y. Bartal, O. Neiman
2008ACM-SIAM Symposium on Discrete Algorithms43 citations
Semantic Scholar
Light Spanners
Michael Elkin, O. Neiman, Shay Solomon
2014SIAM Journal on Discrete Mathematics40 citations
Semantic Scholar
Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC
Michael Elkin, O. Neiman
2019Distributed computing38 citations
Semantic Scholar
Near Linear Lower Bound for Dimension Reduction in L1
Alexandr Andoni, M. Charikar, O. Neiman, Huy L. Nguyen
2011IEEE Annual Symposium on Foundations of Computer Science37 citations
Semantic Scholar
Covering Metric Spaces by Few Trees
Y. Bartal, Ora Nova Fandina, O. Neiman
2019International Colloquium on Automata, Languages and Programming35 citations
Semantic Scholar
Beck's Three Permutations Conjecture: A Counterexample and Some Consequences
Alantha Newman, O. Neiman, Aleksandar Nikolov
2012IEEE Annual Symposium on Foundations of Computer Science33 citations
Semantic Scholar
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
Y. Bartal, Arnold Filtser, O. Neiman
2016ACM-SIAM Symposium on Discrete Algorithms28 citations Open access
Semantic Scholar
Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory
Michael Elkin, O. Neiman
2017arXiv.org27 citations
Semantic Scholar
Light Spanners for High Dimensional Norms via Stochastic Decompositions
Arnold Filtser, O. Neiman
2018Algorithmica26 citations Open access
Semantic Scholar
Ramsey Spanning Trees and Their Applications
Ittai Abraham, S. Chechik, Michael Elkin, Arnold Filtser +1 more
2017ACM-SIAM Symposium on Discrete Algorithms26 citations Open access
Semantic Scholar
On efficient distributed construction of near optimal routing schemes
Michael Elkin, O. Neiman
2016Distributed computing26 citations
Semantic Scholar
Prioritized Metric Structures and Embedding
Michael Elkin, Arnold Filtser, O. Neiman
2015Symposium on the Theory of Computing26 citations Open access
Semantic Scholar
Improved weighted additive spanners
Michael Elkin, Yuval Gitlitz, O. Neiman
2020Distributed computing25 citations Open access
Semantic Scholar
Metric embedding via shortest path decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta, O. Neiman
2017Symposium on the Theory of Computing24 citations Open access
Semantic Scholar
Near-Additive Spanners and Near-Exact Hopsets, A Unified View
Michael Elkin, O. Neiman
2020Bull. EATCS20 citations
Semantic Scholar
Almost Shortest Paths with Near-Additive Error in Weighted Graphs
Michael Elkin, Yuval Gitlitz, O. Neiman
2019Scandinavian Workshop on Algorithm Theory20 citations
Semantic Scholar
Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs
Michael Elkin, Yuval Gitlitz, O. Neiman
2019arXiv.org20 citations
Semantic Scholar
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp
Y. Bartal, Lee-Ad Gottlieb, O. Neiman
2013SIAM Journal on Discrete Mathematics18 citations
Semantic Scholar
Local Embeddings of Metric Spaces
Ittai Abraham, Y. Bartal, O. Neiman
2007Algorithmica18 citations Open access
Semantic Scholar
Near-Optimal Distributed Routing with Low Memory
Michael Elkin, O. Neiman
2018ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing17 citations
Semantic Scholar
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
O. Neiman, Shay Solomon
2016TALG17 citations Open access
Semantic Scholar
Distributed Strong Diameter Network Decomposition: Extended Abstract
Michael Elkin, O. Neiman
2016ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing15 citations
Semantic Scholar
Space-efficient path-reporting approximate distance oracles
Michael Elkin, O. Neiman, Christian Wulff-Nilsen
2014Theoretical Computer Science15 citations Open access
Semantic Scholar
Dimensionality reduction: theoretical perspective on practical measures
Y. Bartal, Nova Fandina, O. Neiman
2019Neural Information Processing Systems13 citations
Semantic Scholar
Low Dimensional Embeddings of Doubling Metrics
O. Neiman
2013Theory of Computing Systems13 citations
Semantic Scholar
Distributed Construction of Light Networks
Michael Elkin, Arnold Filtser, O. Neiman
2019ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing12 citations Open access
Semantic Scholar
On vertex rankings of graphs and its relatives
Ilan Karpas, O. Neiman, Shakhar Smorodinsky
2015Discrete Mathematics11 citations Open access
Semantic Scholar
On low dimensional local embeddings
Ittai Abraham, Y. Bartal, O. Neiman
2009ACM-SIAM Symposium on Discrete Algorithms11 citations
Semantic Scholar
Light, Reliable Spanners
Arnold Filtser, Yuval Gitlitz, O. Neiman
2023International Symposium on Computational Geometry10 citations Open access
Semantic Scholar
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost
Alexandr Andoni, A. Naor, O. Neiman
2016International Colloquium on Automata, Languages and Programming10 citations
Semantic Scholar
On Embedding of Finite Metric Spaces into Hilbert Space
Ittai Abraham, Y. Bartal, O. Neiman
20069 citations
Semantic Scholar
Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication
Michael Elkin, O. Neiman
2022Symposium on Theoretical Aspects of Computer Science8 citations
Semantic Scholar
Dynamic Inefficiency: Anarchy without Stability
Noam Berger, Michal Feldman, O. Neiman, Mishael Rosenthal
2011Algorithmic Game Theory7 citations
Semantic Scholar
Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication
Michael Elkin, O. Neiman
2020arXiv.org6 citations
Semantic Scholar
Lossless Prioritized Embeddings
Michael Elkin, O. Neiman
2019ACM-SIAM Symposium on Discrete Algorithms6 citations Open access
Semantic Scholar
Deterministic Algorithms for Fully Dynamic Maximal Matching
O. Neiman, Shay Solomon
2012arXiv.org6 citations
Semantic Scholar
A Unified Framework for Hopsets
O. Neiman, I. Shabat
2022Embedded Systems and Applications4 citations
Semantic Scholar
Near Isometric Terminal Embeddings for Doubling Metrics
Michael Elkin, O. Neiman
2018Algorithmica4 citations Open access
Semantic Scholar
Bandwidth and low dimensional embedding
Y. Bartal, Douglas E. Carroll, A. Meyerson, O. Neiman
2011Theoretical Computer Science4 citations Open access
Semantic Scholar