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.
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
Symposium on Theory of Computing, STOC 2025 [DOI] [arXiv]
Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan and Oren Weimann
International Colloquium on Automata, Languages, and Programming, ICALP 2025 [DOI] [arXiv]
GreedyMini: Generating low-density DNA minimizers
Shay Golan, Ido Tziony, Matan Kraus, Yaron Orenstein and Arseny Shur
To appear in International Conference on Intelligent Systems for Molecular Biology, ISMB 2025 [bioRxiv]
Covers in Optimal Space
Itai Boneh, and Shay Golan
Combinatorial Pattern Matching, CPM 2025 [DOI]
String Problems in the Congested Clique Model
Shay Golan and Matan Kraus
Combinatorial Pattern Matching, CPM 2025 [DOI] [arXiv]
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
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]
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
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)