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
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
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:
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)