Ofer Neiman's Page















I'm a faculty member at

Computer Science Department
Ben-Gurion University
Beer Sheva
Israel

Email: neimano at cs dot bgu dot ac dot il
Phone: +972-8-6428060
Office: building 37, room 215
Reception hour: Mon. 10-12.

Biography

I received my undergraduate degree in mathematics and computer science from the Hebrew university at Jerusalem, where I stayed to complete a Ph.d in computer science, under the supervision of Prof. Yair Bartal. After one year as a Courant Instructor in New York university, and one year as a research associate at Princeton university and the Center for Computational Intractability, I'm currently a faculty member at Ben Gurion University.

Research Interests

My research focuses on theoretical computer science, more specifically: combinatorics, discrete geometry, metric spaces, and their application to computer science and algorithms

Teaching

- Fall 2012: Approximation Algorithms
- Spring 2012: Discrete Structures and Combinatorics
- Fall 2013: Complexity, Algorithms 2
- Spring 2013: Discrete Structures and Combinatorics
- Fall 2014: Complexity, Algorithms 2
- Spring 2014: Discrete Structures and Combinatorics, Metric Embedding
- Fall 2015: Complexity, Algorithms 2, Randomized Algorithms
- Spring 2015: Discrete Structures and Combinatorics
- Fall 2016: Complexity, Spectral Graph Theory
- Spring 2016: Discrete Structures and Combinatorics
- Fall 2017: Complexity (for cyber program), Algorithms 2
- Spring 2017: Discrete Structures and Combinatorics
- Fall 2018: Complexity (for cyber program), Spectral Graph Theory
- Spring 2018: Discrete Structures and Combinatorics, Inverse Course in Metric Embedding
- Fall 2019: Algorithms 2
- Spring 2019: Discrete Structures and Combinatorics, Topics in randomized algorithms
- Fall 2020: Algorithms 2
- Spring 2020: Discrete Structures and Combinatorics, Metric Embeddings

Online Papers

Ph.d Thesis: A Novel Approach to Embedding of Metric Spaces.
Ofer Neiman, The Hebrew university, Jerusalem, 2010.
Ph.d committee: Prof. Yair Bartal(advisor), Prof. Gil Kalai, Prof. Nati Linial.


Surveys

Near-Additive Spanners and Near-Exact Hopsets, A Unified View.
Michael Elkin and Ofer Neiman
Bulletin of the EATCS volume 130 (2020).
[Survey pdf]


Journal Papers

Advances in Metric Embedding Theory.
Ittai Abraham, Yair Bartal and Ofer Neiman.
Advances in Mathematics, 228(6), pages 3026-3126 (2011).
[abstract] [Journal version pdf]

Assouad's Theorem with Dimension Independent of the Snowflaking.
Assaf Naor and Ofer Neiman.
Revista Matematica Iberoamericana 28(4), pages 1-21 (2012).
[abstract] [Journal version pdf]

Bandwidth and low dimensional embedding.
Yair Bartal, Douglas E. Carroll, Adam Meyerson and Ofer Neiman.
Theoretical Computer Science, 500: 44-56 (2013).
[abstract] [Journal version pdf]

Volume in General Metric Spaces.
Ittai Abraham, Yair Bartal, Ofer Neiman and Leonard Schulman.
Discrete & Computational Geometry, 52(2): 366-389 (2014).
[abstract] [Journal version pdf]

Local Embedding of Metric Spaces.
Ittai Abraham, Yair Bartal and Ofer Neiman.
Algorithmica, 72(2): 539-606 (2015).
[abstract] [Journal version pdf]

Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion.
Ittai Abraham, Yair Bartal and Ofer Neiman.
SIAM Journal on Computing, 44(1): 160-192 (2015).
[abstract] [Journal version pdf]

On Vertex Rankings of Graphs and its Relatives.
Ilan Karpas, Ofer Neiman and Shakhar Smorodinsky.
Discrete Mathematics, 338(8): 1460-1467 (2015).
[abstract] [Journal version pdf]

Light Spanners.
Michael Elkin, Ofer Neiman and Shay Solomon.
SIAM J. Discrete Math. 29(3): 1312-1321 (2015).
[abstract] [full version pdf]

On the Impossibility of Dimension Reduction for Doubling Subsets of Lp.
Yair Bartal, Lee-Ad Gottlieb and Ofer Neiman.
SIAM J. Discrete Math. 29(3): 1207-1222 (2015).
[abstract] [full version pdf]

Low Dimensional Embedding of Doubling Metrics.
Ofer Neiman.
Theory of Computing Systems, 58(1): 133-152 (2016)
[abstract] [Journal version pdf]

Simple Deterministic Algorithms for Fully Dynamic Maximal Matching.
Ofer Neiman and Shay Solomon.
ACM Transactions on Algorithms 12(1): 7:1-7:15 (2016).
[abstract] [Journal version pdf]

Space-Efficient Path-Reporting Approximate Distance Oracles.
Michael Elkin, Ofer Neiman and Christian Wulff-Nilsen.
Theoretical Computer Science 651: 1-10 (2016).
[abstract] [full version pdf]

Terminal Embeddings.
Michael Elkin, Arnold Filtser and Ofer Neiman.
Theoretical Computer Science 697: 1-36 (2017).
[abstract] [full version pdf]

On Efficient Distributed Construction of Near Optimal Routing Schemes.
Michael Elkin and Ofer Neiman.
Distributed Computing 31(2): 119-137 (2018).
[abstract] [full version pdf]

Prioritized Metric Structures and Embedding.
Michael Elkin, Arnold Filtser and Ofer Neiman
SIAM Journal on Computing 47(3): 829-858 (2018).
[abstract] [journal version pdf]

Snowflake universality of Wasserstein spaces.
Alexandr Andoni, Assaf Naor, and Ofer Neiman.
Annales scientifiques de l'ENS 51(3): 657-700 (2018).
[abstract] [full version pdf]

Using Petal-Decompositions to Build a Low Stretch Spanning Tree.
Ittai Abraham and Ofer Neiman.
SIAM Journal on Computing 48(2): 227-248 (2019).
[abstract] [Full version pdf]

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs.
Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman and Kunal Talwar.
SIAM Journal on Computing 48(3): 1120-1145 (2019).
[abstract] [Full version pdf]

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators.
Michael Elkin and Ofer Neiman
ACM Transactions on Algorithms 15(1): 4:1-4:29 (2019).
[abstract][full version pdf]

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion.
Yair Bartal, Arnold Filtser and Ofer Neiman
Journal of Computer and System Sciences 105: 116-129 (2019).
[abstract][full version pdf]

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths.
Michael Elkin and Ofer Neiman.
SIAM Journal on Computing 48(4): 1436-1480 (2019).
[abstract] [Full version pdf]

Ramsey Spanning Trees and their Applications.
Ittai Abraham, Shiri Chechik, Arnold Filtser, Michael Elkin and Ofer Neiman
ACM Transactions on Algorithms 16(2): 19:1-19:21 (2020).
[abstract][Full version pdf]


Conference Papers

Metric Embeddings with Relaxed Guarantees.
I. Abraham, Y. Bartal, T-H. Chan, K. Dhamdhere, A.Gupta, J. Kleinberg, O. Neiman and A. Slivkins.
46th Annual IEEE Symposium on Foundations of Computer Science, October 2005. (FOCS 2005).
[abstract] [FOCS version pdf] [talk: ppt]

Advances in Metric Embedding Theory.
Ittai Abraham, Yair Bartal and Ofer Neiman.
38th ACM Symposium on Theory of Computing, May 2006. (STOC 2006).
[abstract] [STOC version pdf] [talk: ppt]

Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion.
Ittai Abraham, Yair Bartal and Ofer Neiman.
18th ACM-Siam Symposium on Discrete Algorithms, January 2007. (SODA 2007).
[abstract] [Full version pdf] [talk: ppt]

Local Embedding of Metric Spaces.
Ittai Abraham, Yair Bartal and Ofer Neiman.
39th Ann. ACM Symposium on Theory of Computing, June 2007. (STOC 2007)
[abstract] [STOC version pdf]

Embedding Metric Spaces in their Intrinsic Dimension.
Ittai Abraham, Yair Bartal and Ofer Neiman.
19th ACM-Siam Symposium on Discrete Algorithms, January 2008. (SODA 2008).
[abstract] [SODA version pdf]

Nearly Tight Low Stretch Spanning Trees.
Ittai Abraham, Yair Bartal and Ofer Neiman.
49th Annual IEEE Symposium on Foundations of Computer Science, October 2008. (FOCS 2008).
[abstract] [FOCS version pdf] [Full version pdf]

On Low Dimensional Local Embeddings.
Ittai Abraham, Yair Bartal and Ofer Neiman.
20th ACM-Siam Symposium on Discrete Algorithms, January 2009. (SODA 2009).
[abstract] [SODA version pdf]

Volume in General Metric Spaces.
Ittai Abraham, Yair Bartal, Ofer Neiman and Leonard Schulman.
18th Ann. European Symposium on Algorithms, September 2010. (ESA 2010).
[abstract] [ESA version pdf]

Bandwidth and Low Dimensional Embedding.
Yair Bartal, Douglas Carroll, Adam Meyerson and Ofer Neiman.
14th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, August 2011. (APPROX 2011).
[abstract] [APPROX version pdf]

Dynamic Inefficiency: Anarchy without Stability.
Noam Berger, Michal Feldman, Ofer Neiman and Mishael Rosenthal.
4th Symposium on Algorithmic Game Theory, October 2011. (SAGT 2011).
[abstract] [SAGT version pdf] [Full version pdf]

Near Linear Lower Bounds for Dimension Reduction in L1.
Alexandr Andoni, Moses S. Charikar, Ofer Neiman and Huy L. Nguyen.
52th Annual IEEE Symposium on Foundation of Computer Science, October 2011. (FOCS 2011).
[abstract] [FOCS version pdf]

Using Petal-Decompositions to Build a Low Stretch Spanning Tree.
Ittai Abraham and Ofer Neiman.
44th Ann. ACM Symposium on Theory of Computing, June 2012. (STOC 2012).
[abstract] [STOC version pdf] [Full version pdf]

Beck’s Three Permutations Conjecture: A Counterexample and Some Consequences.
Alantha Newman, Ofer Neiman and Alexandar Nikolov.
53th Annual IEEE Symposium on Foundation of Computer Science, October 2012. (FOCS 2012).
[abstract] [FOCS version pdf] [Full version pdf]

Simple Deterministic Algorithms for Fully Dynamic Maximal Matching.
Ofer Neiman and Shay Solomon.
45th Ann. ACM Symposium on Theory of Computing, June 2013. (STOC 2013).
[abstract] [STOC version pdf]

Low Dimensional Embedding of Doubling Metrics.
Ofer Neiman.
11th Workshop on Approximation and Online Algorithms, September 2013. (WAOA 2013).
[abstract] [full version pdf]

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs.
Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman and Kunal Talwar.
46th Ann. ACM Symposium on Theory of Computing, June 2014. (STOC 2014).
[abstract] [full version pdf]

On the Impossibility of Dimension Reduction for Doubling Subsets of Lp.
Yair Bartal, Lee-Ad Gottlieb and Ofer Neiman.
30th Annual Symposium on Computational Geometry, June 2014. (SOCG 2014).
[abstract] [full version pdf]

Light Spanners.
Michael Elkin, Ofer Neiman and Shay Solomon.
41st International Colloquium on Automata, Languages, and Programming, July 2014. (ICALP 2014).
[abstract] [full version pdf]

Prioritized Metric Structures and Embedding.
Michael Elkin, Arnold Filtser and Ofer Neiman
47th Ann. ACM Symposium on Theory of Computing, June 2015. (STOC 2015).
[abstract] [full version pdf]

Terminal Embeddings.
Michael Elkin, Arnold Filtser and Ofer Neiman
18th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, August 2015. (APPROX 2015).
[abstract] [full version pdf]

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion.
Yair Bartal, Arnold Filtser and Ofer Neiman
27th ACM-Siam Symposium on Discrete Algorithms, January 2016. (SODA 2016).
[abstract][full version pdf]

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost.
Alex Andoni, Assaf Naor and Ofer Neiman
43rd International Colloquium on Automata, Languages and Programming, July 2016. (ICALP 2016).
[abstract][conf. version pdf]

On Efficient Distributed Construction of Near Optimal Routing Schemes.
Michael Elkin and Ofer Neiman
35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. (PODC 2016).
[abstract][full version pdf]

Distributed Strong Diameter Network Decomposition.
Michael Elkin and Ofer Neiman
35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. (PODC 2016).
[abstract][full version pdf]

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths.
Michael Elkin and Ofer Neiman
57th Annual IEEE Symposium on Foundation of Computer Science, October 2016. (FOCS 2016).
[abstract][full version pdf]

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators.
Michael Elkin and Ofer Neiman
28th ACM-Siam Symposium on Discrete Algorithms, January 2017. (SODA 2017).
[abstract][full version pdf]

Ramsey Spanning Trees and their Applications.
Ittai Abraham, Shiri Chechik, Arnold Filtser, Michael Elkin and Ofer Neiman
29th ACM-Siam Symposium on Discrete Algorithms, January 2018. (SODA 2018).
[abstract][SODA version pdf]

Near Isometric Terminal Embeddings for Doubling Metrics.
Michael Elkin and Ofer Neiman.
34th Annual Symposium on Computational Geometry, June 2018. (SOCG 2018).
[abstract] [full version pdf]

Metric Embedding via Shortest Path Decompositions .
Ittai Abraham, Arnold Filtser, Anupam Gupta and Ofer Neiman.
50th Ann. ACM Symposium on Theory of Computing, June 2018. (STOC 2018).
[abstract][full version pdf]

Near-Optimal Distributed Routing with Low Memory.
Michael Elkin and Ofer Neiman
37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. (PODC 2018).
[abstract][full version pdf]

Light Spanners for High Dimensional Norms via Stochastic Decompositions.
Arnold Filtser and Ofer Neiman
26th Ann. European Symposium on Algorithms, August 2018. (ESA 2018).
[abstract][full version pdf]

Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC.
Michael Elkin and Ofer Neiman
31st ACM on Symposium on Parallelism in Algorithms and Architectures, June 2019. (SPAA 2019).
[abstract][full version pdf]

Covering Metric Spaces by Few Trees.
Yair Bartal, Nova Fandina and Ofer Neiman
46rd International Colloquium on Automata, Languages and Programming, July 2019. (ICALP 2019).
[abstract][full version pdf]

Dimensionality Reduction: Theoretical Perspective on Practical Measures.
Yair Bartal, Nova Fandina and Ofer Neiman
33rd Conference on Neural Information Processing Systems, December 2019. (NIPS 2019)
[abstract]

Lossless Prioritized Embeddings.
Michael Elkin and Ofer Neiman
31th ACM-Siam Symposium on Discrete Algorithms, January 2020. (SODA 2020).
[abstract][SODA version pdf]

Distributed Construction of Light Networks.
Michael Elkin, Arnold Filtser and Ofer Neiman
39th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. (PODC 2020).
[abstract][full version pdf]