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

2024:
- String 2-Covers with No Length Restrictions
  Itai Boneh, Shay Golan and Arseny Shur
  European Symposium on Algorithms, ESA 2024 [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]
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 (just accepted) [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]

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)