List of publications

Conference Papers

  1. What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs? Amir Abboud, Shay Mozes, and Oren Weimann. n Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023). 4:1-4:20.
  2. On the Hardness of Computing the Edit Distance of Shallow Trees. Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. In Proceedings of The 29th annual Symposium on String Processing and Information Retrieval (SPIRE 2022). 290-302. pdf version
  3. Improved Compression of the Okamura-Seymour Metric. Shay Mozes, Nathan Wallheimer, and Oren Weimann. In Proceedings of The 33rd International Symposium on Algorithms and Computation (ISAAC 2022). 27:1-27:19.
  4. The Fine-Grained Complexity of Episode Matching. Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner, and Oren Weimann. In Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, (CPM 2022). 4:1-4:12.
  5. Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs. Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen. In Proceedings of the 32nd International Symposium on Algorithms and Computation, (ISAAC 2021). 25:1-25:12. pdf version   slides.
  6. A Faster Algorithm for Max Flow in Directed Planar Graphs with Vertex Capacities. Julian Enoch, Kyle Fox, Dor Mesica, Shay Mozes. In Proceedings of the 32nd International Symposium on Algorithms and Computation, (ISAAC 2021). 72:1-72:16.
  7. An Almost Optimal Edit Distance Oracle. Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP 2021). 48(1)-48(20). pdf version  
  8. Fault-Tolerant Distance Labeling for Planar Graphs. Aviv Bar-Natan, Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. In Proceedings of the 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021). 315-333 pdf version  
  9. Planar Negative k-cycle. Paweł Gawrychowski, Shay Mozes, and Oren Weimann. In Proceedings of the 32th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021). 2017--2024. pdf version  
  10. A Note on a Recent Algorithm for Minimum Cut. Paweł Gawrychowski, Shay Mozes, and Oren Weimann. In Proceedings of the 4th Symposium on Simplicity in Algorithms, (SOSA 2021). 74--79. arXiv:cs.ds/2008.02060 pdf version  
  11. Recipient of the ICALP 2020 best paper award (track A):
    Minimum Cut in O(n log2n) Time. Paweł Gawrychowski, Shay Mozes, and Oren Weimann. In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), 57:1-57:15. arXiv:cs.ds/1911.01145 pdf version  
  12. Dynamic String Alignment. Panagiotis Charalampopoulos, Tomasz Kociumaka, and Shay Mozes. In Proceedings of the 31th Annual Symposium on Combinatorial Pattern Matching (CPM 2020), 9:1-9:13. pdf version  
  13. Almost optimal distance oracles for planar graphs. Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. In Proceedings of the 51st Annual ACM on Symposium on Theory of Computing (STOC 2019), 138-151. arXiv:cs.ds/1811.01551 pdf version talk(video)  
  14. Exact Distance Oracles for Planar Graphs with Failing Vertices. Panagiotis Charalampopoulos, Shay Mozes, and Benjamin Tebeka. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019). 2110-2123. arXiv:cs.ds/1807.05968 pdf version  
  15. Compressed Range Minimum Queries. Seungbum Jo, Shay Mozes, and Oren Weimann. In Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), 206-217. pdf version  
  16. Near-Optimal Distance Emulator for Planar Graphs. Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), 16:1-16:17 . arXiv:cs.ds/1807.01478 pdf version  
  17. Better Tradeoffs for Exact Distance Oracles in Planar Graphs. Paweł Gawrychowski, Shay Mozes, Oren Weimann and Christian Wulff-Nilsen. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 515-529.  arXiv:cs.ds/1708.01386 pdf version  
  18. Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n5/3) time. Haim Kaplan, Paweł Gawrychowski, Shay Mozes, Micha Sharir and Oren Weimann. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 495-514.  arXiv:cs.ds/1704.02793
  19. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). Karl Bringmann, Paweł Gawrychowski, Shay Mozes and Oren Weimann. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 1190-1206.  arXiv:cs.ds/1703.08940
  20. Near-Optimal Compression for the Planar Graph Metric. Amir Abboud, Paweł Gawrychowski, Shay Mozes and Oren Weimann. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 530-549.  arXiv:cs.ds/1703.04814
  21. Minimum Cut of Directed Planar Graphs in O(nloglogn) Time . Shay Mozes, Cyril Nikolaev, Yahav Nussbaum and Oren Weimann. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 477-494.  arXiv:cs.ds/1512.02068
  22. Efficient Dynamic Vertex-Label Distance Oracles for Planar Graphs. Itay Laish and Shay Mozes. In proceedings of the 15th International Workshop on Approximation and Online Algorithms (WAOA 2017). To appear. arXiv:cs.ds/1707.02414.
  23. Dispersion on Trees. . Paweł Gawrychowski, Nadav Krasnopolsky, Shay Mozes and Oren Weimann. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017). To appear. arXiv:cs.ds/1706.09185.
  24. The Nearest Colored Node in a Tree. . Paweł Gawrychowski, Gad M. Landau, Shay Mozes and Oren Weimann. In Proceedings of the 27th Annual symposium on Combinatorial Pattern Matching (CPM 2016). 25:1-25:12. pdf version  
  25. Efficient Vertex-Label Distance Oracles for Planar Graphs. Shay Mozes and Eyal E. Skop. In proceedings of the 13th International Workshop on Approximation and Online Algorithms (WAOA 2015). pages 97-109. arXiv:cs.ds/1504.04690. slides.
  26. Submatrix Maximum Queries in Monge Matrices are Equivalent to Predecessor Search. . Paweł Gawrychowski, Shay Mozes and Oren Weimann. In proceedings of the 42n International Colloquium on Automata, Languages, and Programming (ICALP 2015). pages 580-592. arXiv:cs.ds/1502.07663 pdf version  
  27. A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. Kyle Fox, Philip Klein, and Shay Mozes. In proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015). pages 841-850. arXiv:cs.ds/1504.08008   ACM DL Author-ize service
  28. Improved Submatrix Maximum Queries in Monge Matrices. Paweł Gawrychowski, Shay Mozes and Oren Weimann. In proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014). pages 525-537   pdf version  
  29. Structured Recursive Separator Decompositions for Planar Graphs in Linear Time. Philip Klein, Shay Mozes and Christian Sommer. In proceedings of the 45th ACM Symposium on Theory of Computing (STOC 2013). pages 505-514. ACM DL Author-ize service
  30. Short and Simple Cycle Separators in Planar Graphs. Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, and Christian Sommer. In Proceedings of the 15th Workshop on Algorithm Engineering and Experiments (ALENEX 2013), pages 26-40. pdf version  
  31. Submatrix Maximum Queries in Monge Matrices and Monge Partial Matrices, and Their Applications. Haim Kaplan, Shay Mozes, Yahav Nussbaum and Micha Sharir. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 338-355.  pdf version  
  32. Exact Distance Oracles for Planar Graphs. Shay Mozes and Christian Sommer. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 209-222.  arXiv:cs.ds/1011.5549 pdf version  
  33. Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. Glencora Borradaile, Philip Klein, Shay Mozes, Yahav Nussbaum and Christian Wulff-Nilsen. in Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pages 170-179. arXiv:cs.dm/1105.2228 pdf version slides
  34. Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter n log n) Time. Philip Klein and Shay Mozes. In Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), pages 571-582. pdf version  
  35. The Train Delivery Problem - Vehicle Routing Meets Bin Packing. Aparna Das, Claire Mathieu and Shay Mozes. In Proceedings of the 8th Workshop on Approximation and Online Algorithms (WAOA 2010), pages 94-105. pdf version  
  36. Recipient of the ESA 2010 best student paper award:
    Shortest Paths in Planar Graphs with Real Lengths in O(n log2n / loglog n) Time. Shay Mozes and Christian Wulff-Nilsen. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010), pages 206-217. pdf version  
  37. Efficient Algorithms for Analyzing Segmental Duplications, Deletions, and Inversions in Genomes. Crystal Kahn, Shay Mozes and Ben Raphael. In Proceedings of the 9th International Workshop (WABI 2009), pages 169-180  pdf version slides
  38. Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(n log2 n)-Time Algorithm. Philip Klein, Shay Mozes and Oren Weimann. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pages 236-245.  pdf version slides
  39. Fast Algorithms for Computing Tree LCS. Shay Mozes, Dekel Tsur , Oren Weimann and Michal Ziv-Ukelson. In Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (CPM 2008), pages 230-243.  pdf version
  40. Finding an Optimal Tree Searching Strategy in Linear Time. Shay Mozes, Krzysztof Onak and Oren Weimann. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pages 1096-1105.   pdf version slides   comment
  41. Recipient of the CPM 2007 best paper award:
    Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions. Shay Mozes, Oren Weimann and Michal Ziv-Ukelson. In Proceedings of the 18th annual symposium on Combinatorial Pattern Matching (CPM 2007), pages 4-15.  pdf version slides C++/Java Implementation
  42. An Optimal Decomposition Algorithm for Tree Edit Distance. Erik Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), pages 146-157.  arXiv:cs.ds/0604037 pdf version slides

Journal Articles

  1. Almost Optimal Exact Distance Oracles for Planar Graphs. Panagiotis Charalampopoulos, Paweł Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, and Oren Weimann. Journal of the ACM (JACM): 70(2): 12:1--12:50 (2023) ACM DL Author-ize service
  2. Fault-Tolerant Distance Labeling for Planar Graphs. Aviv Bar-Natan, Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Theoretical Computer Science (TCS) 918: 48-59 (2022) pdf version  
  3. Exact Distance Oracles for Planar Graphs with Failing Vertices. Panagiotis Charalampopoulos, Shay Mozes, and Benjamin Tebeka. ACM Transactions on Algorithms (TALG): 18(2): 18:1--18:23 (2022) ACM DL Author-ize service
  4. Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n5/3) time. Haim Kaplan, Paweł Gawrychowski, Shay Mozes, Micha Sharir and Oren Weimann. SIAM Journal on Computing (SICOMP) 50(2), 509-554 (2021).  pdf version
  5. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). Karl Bringmann, Paweł Gawrychowski, Shay Mozes and Oren Weimann. ACM Transactions on Algorithms (TALG): 16(4): 48 (2020) ACM DL Author-ize service
  6. Submatrix Maximum Queries in Monge Matrices are Equivalent to Predecessor Search. . Paweł Gawrychowski, Shay Mozes and Oren Weimann. ACM Transactions on Algorithms (TALG): 16(2): 16 (2020) ACM DL Author-ize service
  7. Compressed Range Minimum Queries. Seungbum Jo, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Theoretical Computer Science (TCS) 812: 39-48 (2020) pdf version  
  8. Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs. Itay Laish and Shay Mozes Theory of Computing Systems 63(8): 1849-1874 (2019) pdf version  
  9. Efficient Vertex-Label Distance Oracles for Planar Graphs. Shay Mozes and Eyal E. Skop. Theory of Computing Systems 62(2): 419-440 (2018) pdf version  
  10. Faster Shortest Paths in Dense Distance Graphs, with Applications. Shay Mozes, Yahav Nussbaum and Oren Weimann. Theoretical Computer Science (TCS) 711: 11-35 (2018). arXiv:cs.ds/1404.0977 pdf version  
  11. The Nearest Colored Node in a Tree. . Paweł Gawrychowski, Gad M. Landau, Shay Mozes and Oren Weimann. Theoretical Computer Science (TCS). 710: 66-73 (2018). pdf version  
  12. Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. Glencora Borradaile, Philip Klein, Shay Mozes, Yahav Nussbaum and Christian Wulff-Nilsen. SIAM Journal on Computing (SICOMP) 46(4), 1280-1303 (2017).  pdf version
  13. Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications. Haim Kaplan, Shay Mozes, Yahav Nussbaum and Micha Sharir. ACM Transactions on Algorithms (TALG): 13 (2):26 (2017).  ACM DL Author-ize service
  14. Short and Simple Cycle Separators in Planar Graphs. Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, and Christian Sommer. Invited submission to ACM Journal of Experimental Algorithmics special issue for ALENEX 2013 (JEA), 21(1):2.2 (2016).  ACM DL Author-ize service
  15. Efficient Algorithms for Analyzing Segmental Duplications with Deletions and Inversions in Genomes . Crystal Kahn, Shay Mozes and Ben Raphael. Algorithms for Molecular Biology 2010, 5:11.  pdf version
  16. Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(n log2 n)-Time Algorithm. Philip Klein, Shay Mozes and Oren Weimann. Invited submission to ACM Transactions on Algorithms special issue for SODA 2009 (TALG), 6(2): (2010).  ACM DL Author-ize service
  17. Fast Algorithms for Computing Tree LCS. Shay Mozes, Dekel Tsur , Oren Weimann and Michal Ziv-Ukelson. Theoretical Computer Science, 410 (43): 4303-4314 (2009)  pdf version
  18. An Optimal Decomposition Algorithm for Tree Edit Distance. Erik Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann. ACM Transactions on Algorithms (TALG), 6(1): (2009).  ACM DL Author-ize service
  19. Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions. Shay Mozes, Yury Lifshits , Oren Weimann and Michal Ziv-Ukelson. Algorithmica, Vol.54 (3) (2009), Page 379 .  pdf version Algorithmica C++/Java Implementation
  20. A new construction for a QMA complete 3-local Hamiltonian. Daniel Nagaj and Shay Mozes. J. Math. Phys. 48, 072104 (2007). J.Math.Phys.  arXiv:quant-ph/0612113
  21. Deterministic Dense Coding with Partially Entangled states. Shay Mozes, Jonathan Oppenheim and Benni Reznik. Phys. Rev.  A. 71, 012311, (2005).  PRA  arXiv:quant-ph/0403189
  22. The effect of unitary noise on Grover's quantum search algorithm. Daniel Shapira, Shay Mozes and Ofer Biham. Phys. Rev.  A. 67, 042301, (2003).   PRA  arXiv:quant-ph/0307142

Book Chapters

  1. Recursive Separator Decompositions for Planar Graphs. Shay Mozes. Encyclopedia of Algorithms 2015.

Book Draft

  1. Optimization Algorithms for Planar Graphs. Philip Klein and Shay Mozes. draft available online.

smozesidcacil

Home