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-6428113
Office: building 37, room 215

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

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.

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 (2012), no. 4, pages 1-21.
[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.
Transactions on Algorithms 12(1): 7 (2016).
[abstract] [Journal version pdf]

Space-Efficient Path-Reporting Approximate Distance Oracles.
Michael Elkin, Ofer Neiman and Christian Wulff-Nilsen.
To appear in Theoretical Computer Science.
[abstract] [full version pdf]

Snowflake universality of Wasserstein spaces.
Alexandr Andoni, Assaf Naor, and Ofer Neiman.
To appear in Annales scientifiques de l'ENS.
[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]