Omer Gold, PhD

Email: omer (at)

Academic Email: (at)

View Omer Gold's profile on LinkedIn


Founder of a startup, currently in stealth mode.

I have recently obtained my PhD from the School of Computer Science at Tel Aviv University, where my advisor was Prof. Micha Sharir.
Here, you can find my dissertation: New Algorithms for Some Classical Problems in P. (Abstract, Acknowledgements)
I recieved my M.Sc. in Computer Science (magna cum laude) from Bar-Ilan University,
and my B.Sc. in Mathematics and Computer Science from Ben Gurion University.

During my PhD studies I have worked on some of the core problems in the field of algorithm design, which yielded the following results.
1) Improved algorithm and decision tree for the 3SUM problem (both were later further improved).
2) The first subquadratic-time algorithm for computing Dynamic Time Warping between two point-sequences on the line,
    breaking a 50 years old quadratic time barrier. This is the best-known algorithm for this problem to date.
3) The first strongly-polynomial subcubic-time algorithm for computing L Closest Pair of n points in Rn.
4) Proofs of the existence of various Diameter Spanners in directed graphs, and efficient algorithms to compute them.

Below, you can find the papers that include the results mentioned above, as well as additional papers.


Research interests: Design and Analysis of Algorithms, Computational Geometry.


Omer Gold
PhD Dissertation: "New Algorithms for Some Classical Problems in P"  PDF
Tel Aviv University, 2020.

Keerti Choudhary and Omer Gold
"Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms"  PDF
In Proc. of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).
Also in arXiv:1812.01602.

Omer Gold and Micha Sharir
"Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier"  PDF
ACM Transactions on Algorithms, Volume 14 Issue 4, October 2018 (TALG 2018)
Also in Proc. of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Also in arXiv:1607.05994

Omer Gold and Micha Sharir
"Dominance Product and High-Dimensional Closest Pair under L"  PDF
In Proc. of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Also in arXiv:1605.08107

Omer Gold and Micha Sharir
"Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy"  PDF
In Proc. of the 25th Annual European Symposium on Algorithms (ESA 2017)
Also in arXiv:1512.05279

Omer Gold and Micha Sharir
"On the Complexity of the Discrete Fréchet Distance under L1 and L"  PDF
The 31st European Workshop on Computational Geometry (EuroCG 2015)

Omer Gold and Reuven Cohen
"Coping with Physical Attacks on Random Network Structures"  PDF
In Proc. of IEEE International Conference on Communications (ICC 2014)
Also in arXiv:1312.6189

Omer Gold
Master's Thesis: "Coping with Physical Attacks on Random Network Structures"  PDF
Bar-Ilan University, 2014.


Omer Gold
"Deep Actor-Critic Experiment for Stock Trading Amid Sentiment and Buzz"  PDF
Preprint based on a project for the "deep learning" graduate course in Tel Aviv University, 2019.


I served as an external reviewer for the following venues: STOC, SODA, SoCG, ISAAC,
and for the International Journal of Computational Geometry and Applications.


Google Technologies for Cloud and Web Development, Tel Aviv University
Fall 2017/18, Spring 2018, Fall 2018/19, Spring 2019, Fall 2019/20, Spring 2020

Discrete Mathematics, Spring 2017, Tel Aviv University

Computational Geometry, Spring 2015, Tel Aviv University

Automata and Formal Languages, Spring 2012, Spring 2013, Bar-Ilan University

Automata and Formal Languages - a summary of my lessons from spring 2012 (PDF).
During my M.Sc. studies in Bar-Ilan University I was a TA for the Automata and Formal Languages course, for which
I wrote the lesson plans that you can find in the link above. I hope that it can be helpful to students of relevant courses.