Publications

• Distributed Maximum Flow in Planar Graphs. With Yaseen Abd-Elhaleem, Michal Dory, Merav Parter
  • In PODC 2025. Slides. Video.

• Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs. With Itai Bone, Shiri Chechik, Shay Golan, Shay Mozes
  • In STOC 2025. Slides. Video.

• Faster Construction of a Planar Distance Oracle with Õ(1) Query Time. With Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan
  • In ICALP 2025. Slides.

• Õptimal Dynamic Time Warping on Run-Length Encoded Strings. With Itai Boneh, Shay Golan, Shay Mozes
  • In ICALP 2024. Slides.

• What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs?. With Amir Abboud, Shay Mozes
  • In ESA 2023. Slides.

• Improved Compression of the Okamura-Seymour Metric. With Shay Mozes, Nathan Wallheimer
  • In ISAAC 2022. Slides.

• On the Hardness of Computing the Edit Distance of Shallow Trees. With Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes
  • In SPIRE 2022. Slides.

• The Fine-Grained Complexity of Episode Matching. With Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner
  • In CPM 2022. Slides. Video.

• Planar Negative k-Cycle. With Paweł Gawrychowski, Shay Mozes
  • In SODA 2021. Slides. Video.

• An Almost Optimal Edit Distance Oracle. With Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes
  • In ICALP 2021. Slides. Video.

• Fault-Tolerant Distance Labeling for Planar Graphs. With Aviv Bar-Natan, Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes
  • In Theoretical Computer Science, 2022, special issue for SIROCCO'21.
  • In SIROCCO 2021. Slides. Video.

• A Note on a Recent Algorithm for Minimum Cut. With Paweł Gawrychowski, Shay Mozes
  • In SOSA 2021. Slides. Video.

• Minimum Cut in O(m log²n) Time. With Paweł Gawrychowski, Shay Mozes
  • In Theory of Computing Systems, 2024, special issue for ICALP'20.
  • In ICALP 2020. Slides. Video. Recipient of the best paper award
  • Invited talk at HALG 2021.

• On the Fine-Grained Complexity of Parity Problems. With Amir Abboud, Shon Feller
  • In ICALP 2020. Slides. Video.

• Incremental Distance Products via Faulty Shortest Paths. With Raphael Yuster.
  • In Information Processing Letters, 2020.

• Almost Optimal Exact Distance Oracles for Planar Graphs. With Panagiotis Charalampopoulos, Paweł Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Christian Wulff-Nilsen
  • In Journal of the ACM (JACM), 2023.
  • In STOC 2019. Slides

• Top Tree Compression of Tries. With Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau.
  • In Algorithmica, 2021.
  • In ISAAC 2019. Slides

• Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n^5/3) Time. With Paweł Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir
  • In SIAM Journal on Computing (SICOMP), 2021.
  • In SODA 2018. Slides

• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). With Karl Bringmann, Paweł Gawrychowski, Shay Mozes
  • In ACM Transactions on Algorithms, 2020.
  • In SODA 2018. Slides

• Near-Optimal Compression for the Planar Graph Metric. With Amir Abboud, Paweł Gawrychowski, Shay Mozes
  • In SODA 2018. Slides

• Minimum Cut of Directed Planar Graphs in O(n loglog n) Time. With Shay Mozes, Kirill Nikolaev, Yahav Nussbaum.
  • In SODA 2018. Slides

• Better Tradeoffs for Exact Distance Oracles in Planar Graphs. With Paweł Gawrychowski, Shay Mozes, Christian Wulff-Nilsen
  • In SODA 2018. Slides

• A Faster FPTAS for #Knapsack. With Paweł Gawrychowski, Liran Markin
  • In ICALP 2018. Slides

• A Faster Construction of Greedy Consensus Trees. With Paweł Gawrychowski, Gad M. Landau, Wing-Kin Sung
  • In ICALP 2018. Slides

• Near-Optimal Distance Emulator for Planar Graphs. With Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes
  • In ESA 2018. Slides

• Compressed Range Minimum Queries. With Paweł Gawrychowski, Seungbum Jo, Shay Mozes.
  • In Theoretical Computer Science, 2020.
  • In SPIRE 2018. Slides

• Optimal Distance Labeling Schemes for Trees. With Ofer Freedman, Paweł Gawrychowski, Patrick K. Nicholson
  • In PODC 2017. Slides

• Dispersion on Trees. With Paweł Gawrychowski, Nadav Krasnopolsky, Shay Mozes
  • In ESA 2017. Slides

• Bookmarks in Grammar-Compressed Strings. With Patrick Hagge Cording, Paweł Gawrychowski.
  • In SPIRE 2016. Slides

• The Nearest Colored Node in a Tree. With Paweł Gawrychowski, Gad M. Landau, Shay Mozes.
  • In Theoretical Computer Science, 2018.
  • In CPM 2016. Slides

• Submatrix Maximum Queries in Monge and Partial Monge Matrices are Equivalent to Predecessor Search. With Paweł Gawrychowski, Shay Mozes.
  • In ACM Transactions on Algorithms, 2020.
  • In ICALP 2015. Slides

• Faster Shortest Paths in Dense Distance Graphs, with Applications. With Shay Mozes, Yahav Nussbaum.
  • In Theoretical Computer Science, 2018.

• Longest Common Extensions in Trees. With Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau.
  • In Theoretical Computer Science, 2016.
  • In CPM 2015. Slides

• Consequences of Faster Alignment of Sequences. With Amir Abboud, Virginia Vassilevska Williams.
  • In ICALP 2014. Slides

• Improved Submatrix Maximum Queries in Monge Matrices. With Paweł Gawrychowski, Shay Mozes.
  • In ICALP 2014. Slides

• Tree Compression with Top Trees. With Philip Bille, Inge Li Gørtz, Gad M. Landau.
  • In Information and Computation, 2015, special issue for ICALP'13.
  • In ICALP 2013. Slides

• Approximating the Diameter of Planar Graphs in Near Linear Time. With Raphael Yuster.
  • In ACM Transactions on Algorithms, 2016.
  • In ICALP 2013. Slides

• Binary Jumbled Pattern Matching on Trees and Tree-Like Structures. With Travis Gagie, Danny Hermelin, Gad M. Landau.
  • In Algorithmica, 2015, special issue for ESA'13.
  • In ESA 2013. Slides

• Improved Bounds for Randomized Preemptive Online Matching. With Leah Epstein, Asaf Levin, Danny Segev.
  • In Information and Computation, 2018.
  • In STACS 2013. Slides

• Approximating the Maximum Consecutive Sub-sums of a Sequence. With Ferdinando Cicalese, Eduardo Laber, Raphael Yuster.
  • In Theoretical Computer Science, 2014.
  • In CPM 2012. Slides

• On Approximating String Selection Problems with Outliers. With Christina Boucher, Gad M. Landau, Avivit Levy, David Pritchard.
  • In Theoretical Computer Science, 2013.
  • In CPM 2012. Slides

• Towards Optimal Packed String Matching. With Oren Ben-Kiki, Philip Bille, Danny Breslauer, Leszek Gasieniec, Roberteo Grossi.
  • In Theoretical Computer Science, 2014.
  • In FSTTCS 2011. Slides

• Distance Oracles for Vertex-Labeled Graphs. With Danny Hermelin, Avivit Levy, Raphael Yuster.
  • In ICALP 2011. Slides

• A Note on Exact Distance Labeling. With David Peleg.
  • In Information Processing Letters, 2011.

• Random Access to Grammar-Compressed Strings and Trees. With Philip Bille, Gad M. Landau, Rajeev Raman, Srinivasa Rao, Kunihiko Sadakane.
  • In SIAM Journal on Computing (SICOMP), 2015.
  • In SODA 2011. Slides

• Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication. With Raphael Yuster.
  • In ACM Transactions on Algorithms, 2013.
  • In FOCS 2010. Slides

• Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(n log²n)-Time Algorithm. With Philip Klein, Shay Mozes.
  • In ACM Transactions on Algorithms, 2010, special issue for SODA'09.
  • In SODA 2009. Slides

• Computing the Girth of a Planar Graph in O(n log n) time. With Raphael Yuster.
  • In SIAM Journal on Discrete Mathematics, 24(2), 2010.
  • In ICALP 2009. Slides

• On Cartesian Trees and Range Minimum Queries. With Erik Demaine, Gad M. Landau.
  • In Algorithmica, 2014.
  • In ICALP 2009. Slides

• The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs. With Jean Cardinal, Erik Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman.
  • In Journal of Combinatorial Optimization, 2013.
  • In WINE 2009. Slides

• Unified Compression-Based Acceleration of Edit-Distance Computation. With Danny Hermelin, Gad M. Landau, Shir Landau.
  • In Algorithmica, 2013.
  • In STACS 2009. Slides

• Fast RNA Structure Alignment for Crossing Input Structures. With Rolf Backofen, Gad M. Landau, Mathias Möhl, Dekel Tsur.
  • In Journal of Discrete Algorithms, 2011, special issue for CPM'09.
  • In CPM 2009. Slides

• Finding an Optimal Tree Searching Strategy in Linear Time. With Shay Mozes, Krzysztof Onak.
  • In SODA 2008. Slides

• Fast Algorithms for Computing Tree LCS. With Shay Mozes, Dekel Tsur, Michal Ziv-Ukelson.
  • In Theoretical Computer Science, 2009.
  • In CPM 2008. Slides

• An Optimal Decomposition Algorithm for Tree Edit Distance. With Erik Demaine, Shay Mozes, Benjamin Rossman.
  • In ACM Transactions on Algorithms, 6(1), 2009.
  • In ICALP 2007. Slides

• The Stackelberg Minimum Spanning Tree Game. With Jean Cardinal, Erik Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman.
  • In Algorithmica, 2011.
  • In WADS 2007. Slides

• Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions. With Yury Lifshit, Shay Mozes, Michal Ziv-Ukelson.
  • In Algorithmica, 2009.
  • In CPM 2007. Slides. Recipient of the best paper award

• Indexing a Dictionary for Subset Matching Queries. With Gad M. Landau, Dekel Tsur.
  • In Algorithms and Applications: Esko Ukkonen Festschrift, 2010.
  • In SPIRE 2007. Slides

• Locality and Gaps in RNA Comparison. With Rolf Backofen, Shihyen Chen, Danny Hermelin, Gad M. Landau, Kaizhong Zhang.
  • In Journal of Computational Biology, 2007.
  • In CPM 2006 and in SPIRE 2005. Slides

• Gene Proximity Analysis Across Whole Genomes via PQ Trees. With Gad M. Landau, Laxmi Parida.
  • In Journal of Computational Biology, 2005.
  • In CPM 2005. Slides