Shay Golan

I am a postdoc at Reichman and Haifa Universities, hosted by Shay Mozes and Oren Weimann. Previously, I was a Fulbright postdoc fellow at the EECS department of University of California, Berkeley where I was hosted by Jelani Nelson.

I finished my PhD at the CS department of Bar-Ilan University where I had the fortune of being advised by Ely Porat and Tsvi Kopelowitz.

My main research area is pattern matching, focusing on streaming algorithms.

I am also interested in data structures, graph algorithms and other discrete algorithms.

Publications

see also my DBLP, Google Scholar and ORCID pages

2025
- Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
  Itai Boneh, Shiri Chechik, Shay Golan, Shay Mozes and Oren Weimann
  To appear in Symposium on Theory of Computing, STOC 2025
- String Problems in the Congested Clique Model
  Shay Golan and Matan Kraus
  To appear in Combinatorial Pattern Matching, CPM 2025
- Expected Density of Random Minimizers
  Shay Golan and Arseny Shur
  International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025 [DOI] [arXiv]
2024:
- String 2-Covers with No Length Restrictions
  Itai Boneh, Shay Golan and Arseny Shur
  European Symposium on Algorithms, ESA 2024 [DOI] [arXiv]
- Õptimal Dynamic Time Warping on Run-Length Encoded Strings
  Itai Boneh, Shay Golan, Shay Mozes and Oren Weimann
  International Colloquium on Automata, Languages, and Programming, ICALP 2024 [DOI] [arXiv]
- Searching 2D-Strings for Matching Frames
  Itai Boneh, Dvir Fried, Shay Golan, Matan Kraus, Adrian Miclaus and Arseny Shur
  Combinatorial Pattern Matching, CPM 2024 [DOI] [arXiv]
- Hairpin Completion Distance Lower Bound
  Itai Boneh, Dvir Fried, Shay Golan and Matan Kraus
  Combinatorial Pattern Matching, CPM 2024 [DOI] [arXiv]
- Burst Edit Distance
  Itai Boneh, Shay Golan, Avivit Levy, Ely Porat and B. Riva Shalom
  String Processing and Information Retrieval, SPIRE 2024 [DOI]
2022:
- An Improved Algorithm for The k-Dyck Edit Distance Problem
  Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat and Tatiana Starikovskaya
  Symposium on Discrete Algorithms, SODA 2022 [DOI] [arXiv] [video] TALG (2024) [DOI]
2020:
- Improved Circular k-Mismatch Sketches
  Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat and Przemyslaw Uznanski
  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020 [DOI] [arXiv] [video]
- Approximating text-to-pattern Hamming distances
  Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz and Ely Porat
  Symposium on Theory of Computing, STOC 2020 [DOI] [arXiv] [video]
- The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time
  Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz and Ely Porat
  Combinatorial Pattern Matching, CPM 2020 [DOI] [arXiv] [video]
- Time-Space Tradeoffs for Finding a Long Common Substring
  Stav Ben Nun, Shay Golan, Tomasz Kociumaka, Matan Kraus
  Combinatorial Pattern Matching, CPM 2020 [DOI] [arXiv]
- Locally Consistent Parsing for Text Indexing in Small Space
  Or Birenzwige, Shay Golan and Ely Porat
  Symposium on Discrete Algorithms, SODA 2020 [DOI] [arXiv]
  Presented as an Highlight Talk in CPM 2020 [video]
2019
- Dynamic Dictionary Matching in the Online Model
  Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz and Ely Porat
  Algorithms and Data Structures - 16th International Symposium, WADS 2019 [DOI]
2018
- Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams
  Shay Golan, Tsvi Kopelowitz and Ely Porat
  International Colloquium on Automata, Languages, and Programming, ICALP 2018 [DOI]
2017
- Real-Time Streaming Multi-Pattern Search for Constant Alphabet
  Shay Golan and Ely Porat
  European Symposium on Algorithms, ESA 2017 [DOI]
2016
- Streaming Pattern Matching with d Wildcards
  Shay Golan, Tsvi Kopelowitz and Ely Porat
  European Symposium on Algorithms, ESA 2016 [DOI] [arXiv] Algorithmica (2019) [DOI]

Preprints

- Generating low-density minimizers
  Shay Golan, Ido Tziony, Matan Kraus, Yaron Orenstein and Arseny Shur
  2024 [bioRxiv]
- Hamming Distance Oracle
  Itai Boneh, Dvir Fried, Shay Golan and Matan Kraus
  2024 [arXiv]
- Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
  Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan and Oren Weimann
  2025 [arXiv]
- Õptimal Algorithm for Fully Dynamic LZ77
  Itai Boneh, Shay Golan and Matan Kraus
  2025 [arXiv]

Teaching

2021:
- Fall - 89220 - Algorithms 1
- Spring - 89120 - Data Structures
- Spring - 89322 - Algorithms 2
2020:
- Fall - 89220 - Algorithms 1
- Spring - 89120 - Data Structures
- Spring - 89322 - Algorithms 2
2019:
- Fall - 89220 - Algorithms 1
- Spring - 89120 - Data Structures
- Spring - 89322 - Algorithms 2
- Summer 89220 - Algorithms 1
2018:
- Fall - 89220 - Algorithms 1
- Fall - 89224 - Computabilty
- Spring - 89120 - Data Structures
- Spring - 89322 - Algorithms 2
- Summer 89220 - Algorithms 1
2017:
- Fall - 89224 - Computabilty
- Spring - 89120 - Data Structures
- Spring - 89322 - Algorithms 2
- Summer 89220 - Algorithms 1
2016:
- Fall - 88170 - Introduction to Computing
- Spring - 89120 - Data Structures
- Summer - 89220 - Algorithms 1

Videos

Locally Consistent Parsing for Text Indexing in Small Space (presented in "Compression + Computation 2022" workshop)
An Improved Algorithm for The k-Dyck Edit Distance Problem (SODA 2022)
Improved Circular k-Mismatch Sketches (APPROX 2020)
Approximating text-to-pattern Hamming distances (STOC 2020)
The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time (CPM 2020)
Locally Consistent Parsing for Text Indexing in Small Space (Highlight talk in CPM 2020)

BIU Algorithms 1 - Recitations (Hebrew)