Shay Golan

• 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

  • 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 

• • Hamming Distance Oracle
    Itai Boneh, Dvir Fried, Shay Golan and Matan Kraus
    2024 [arXiv]

  • The Complexity of Dynamic LZ77 is Θ˜(n^{2/3})
    Itai Boneh, Shay Golan and Matan Kraus
    2025 [PDF]