Shay Mozes

According to our database, Shay Mozes authored at least 66 papers between 2006 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Minimum Cut in O(mlog ² n) Time.

Pawel Gawrychowski, Shay Mozes, Oren Weimann

Theory Comput. Syst., August, 2024

Õptimal Dynamic Time Warping on Run-Length Encoded Strings.

Itai Boneh, Shay Golan, Shay Mozes, Oren Weimann

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Almost Optimal Exact Distance Oracles for Planar Graphs.

Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, Christian Wulff-Nilsen

J. ACM, April, 2023

Õptimal Fault-Tolerant Reachability Labeling in Planar Graphs.

Shiri Chechik, Shay Mozes, Oren Weimann

CoRR, 2023

Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings.

Itai Boneh, Shay Golan, Shay Mozes, Oren Weimann

CoRR, 2023

What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?

Amir Abboud, Shay Mozes, Oren Weimann

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Fault-tolerant distance labeling for planar graphs.

Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann

Theor. Comput. Sci., 2022

Exact Distance Oracles for Planar Graphs with Failing Vertices.

Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka

ACM Trans. Algorithms, 2022

On the Hardness of Computing the Edit Distance of Shallow Trees.

Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the String Processing and Information Retrieval, 2022

Improved Compression of the Okamura-Seymour Metric.

Shay Mozes, Nathan Wallheimer, Oren Weimann

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

The Fine-Grained Complexity of Episode Matching.

Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner, Oren Weimann

Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, 2022

2021

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n^5/3) Time.

Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann

SIAM J. Comput., 2021

A Conditional Lower Bound for Episode Matching.

Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner, Oren Weimann

CoRR, 2021

A Note on Maximum Integer Flows in Directed Planar Graphs with Vertex Capacities.

Dor Mesica, Shay Mozes

CoRR, 2021

A Note on a Recent Algorithm for Minimum Cut.

Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Planar Negative <i>k</i>-Cycle.

Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs.

Viktor Fredslund-Hansen, Shay Mozes, Christian Wulff-Nilsen

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities.

Julian Enoch, Kyle Fox, Dor Mesica, Shay Mozes

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

An Almost Optimal Edit Distance Oracle.

Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Compressed range minimum queries.

Pawel Gawrychowski, Seungbum Jo, Shay Mozes, Oren Weimann

Theor. Comput. Sci., 2020

Submatrix Maximum Queries in Monge and Partial Monge Matrices Are Equivalent to Predecessor Search.

Pawel Gawrychowski, Shay Mozes, Oren Weimann

ACM Trans. Algorithms, 2020

Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can).

Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann

ACM Trans. Algorithms, 2020

Minimum Cut in O(m log² n) Time.

Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Dynamic String Alignment.

Panagiotis Charalampopoulos, Tomasz Kociumaka, Shay Mozes

Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

2019

Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs.

Itay Laish, Shay Mozes

Theory Comput. Syst., 2019

Minimum Cut in O(m log²n) Time.

Pawel Gawrychowski, Shay Mozes, Oren Weimann

CoRR, 2019

Almost optimal distance oracles for planar graphs.

Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

Faster shortest paths in dense distance graphs, with applications.

Shay Mozes, Yahav Nussbaum, Oren Weimann

Theor. Comput. Sci., 2018

The nearest colored node in a tree.

Pawel Gawrychowski, Gad M. Landau, Shay Mozes, Oren Weimann

Theor. Comput. Sci., 2018

Efficient Vertex-Label Distance Oracles for Planar Graphs.

Shay Mozes, Eyal E. Skop

Theory Comput. Syst., 2018

Compressed Range Minimum Queries.

Seungbum Jo, Shay Mozes, Oren Weimann

Proceedings of the String Processing and Information Retrieval, 2018

Minimum Cut of Directed Planar Graphs in <i>O</i>(<i>n</i> log log <i>n</i>) Time.

Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, Oren Weimann

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Better Tradeoffs for Exact Distance Oracles in Planar Graphs.

Pawel Gawrychowski, Shay Mozes, Oren Weimann, Christian Wulff-Nilsen

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic <i>Õ</i>(<i>n</i>^5/3) Time.

Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Compression for the Planar Graph Metric.

Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Distance Emulator for Planar Graphs.

Hsien-Chih Chang, Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications.

Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir

ACM Trans. Algorithms, 2017

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time.

Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen

SIAM J. Comput., 2017

Efficient Approximate Distance Oracles for Vertex-Labeled Planar Graphs.

Itay Laish, Shay Mozes

CoRR, 2017

Dispersion on Trees.

Pawel Gawrychowski, Nadav Krasnopolsky, Shay Mozes, Oren Weimann

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

Recursive Separator Decompositions for Planar Graphs.

Shay Mozes

Encyclopedia of Algorithms, 2016

Short and Simple Cycle Separators in Planar Graphs.

Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, Christian Sommer

ACM J. Exp. Algorithmics, 2016

2015

Minimum Cut of Directed Planar Graphs in O(nloglogn) Time.

Shay Mozes, Cyril Nikolaev, Yahav Nussbaum, Oren Weimann

CoRR, 2015

A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection.

Kyle Fox, Philip N. Klein, Shay Mozes

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search.

Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Improved Submatrix Maximum Queries in Monge Matrices.

Pawel Gawrychowski, Shay Mozes, Oren Weimann

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs.

Shay Mozes

PhD thesis, 2013

Improved Submatrix Maximum Queries in Monge Matrices.

Shay Mozes, Oren Weimann

CoRR, 2013

Structured recursive separator decompositions for planar graphs in linear time.

Philip N. Klein, Shay Mozes, Christian Sommer

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Exact distance oracles for planar graphs.

Shay Mozes, Christian Sommer

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications.

Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time.

Philip N. Klein, Shay Mozes

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

2010

Shortest paths in directed planar graphs with negative lengths: A linear-space <i>O</i>(<i>n</i> log² <i>n</i>)-time algorithm.

Philip N. Klein, Shay Mozes, Oren Weimann

ACM Trans. Algorithms, 2010

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in $O(n^{1.5} \log n)$ Time

Shay Mozes

CoRR, 2010

Exact Shortest Path Queries for Planar Graphs Using Linear Space

Shay Mozes, Christian Sommer

CoRR, 2010

Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time

Philip N. Klein, Shay Mozes

CoRR, 2010

Efficient algorithms for analyzing segmental duplications with deletions and inversions in genomes.

Crystal L. Kahn, Shay Mozes, Benjamin J. Raphael

Algorithms Mol. Biol., 2010

The Train Delivery Problem - Vehicle Routing Meets Bin Packing.

Aparna Das, Claire Mathieu, Shay Mozes

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Shortest Paths in Planar Graphs with Real Lengths in <i>O</i>(<i>n</i>log²<i>n</i>/loglog<i>n</i>) Time.

Shay Mozes, Christian Wulff-Nilsen

Proceedings of the Algorithms, 2010

2009

Fast algorithms for computing tree LCS.

Shay Mozes, Dekel Tsur, Oren Weimann, Michal Ziv-Ukelson

Theor. Comput. Sci., 2009

An optimal decomposition algorithm for tree edit distance.

Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann

ACM Trans. Algorithms, 2009

Shortest Paths in Planar Graphs with Real Lengths in $O(n\log^2n/\log\log n)$ Time

Shay Mozes, Christian Wulff-Nilsen

CoRR, 2009

Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions.

Yury Lifshits, Shay Mozes, Oren Weimann, Michal Ziv-Ukelson

Algorithmica, 2009

2008

Finding an optimal tree searching strategy in linear time.

Shay Mozes, Krzysztof Onak, Oren Weimann

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions.

Shay Mozes, Oren Weimann, Michal Ziv-Ukelson

Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

2006

An O(n^3)-Time Algorithm for Tree Edit Distance

Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann

CoRR, 2006