Publications (23)
Structured Recursive Separator Decompositions for Planar Graphs in Linear Time
Philip N. Klein, Shay Mozes, Christian Sommer
Exact Distance Oracles for Planar Graphs
Shay Mozes, Christian Sommer
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
Karl Bringmann, PaweÅ Gawrychowski, Shay Mozes +1
Improved Submatrix Maximum Queries in Monge Matrices
Pawel Gawrychowski, Shay Mozes, Oren Weimann
Minimum Cut of Directed Planar Graphs in O(nloglogn) Time
Shay Mozes, Cyril Nikolaev, Yahav Nussbaum +1
Submatrix Maximum Queries in Monge Matrices are Equivalent to Predecessor Search
Pawel Gawrychowski, Shay Mozes, Oren Weimann
Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs
Itay Laish, Shay Mozes
Shortest Paths in Planar Graphs with Real Lengths in $O(n\log^2n/\log\log n)$ Time
Shay Mozes, Christian Wulff-Nilsen
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Kyle Fox, Philip N. Klein, Shay Mozes
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in $O(n^{1.5} \log n)$ Time
Shay Mozes
An O(n^3)-Time Algorithm for Tree Edit Distance
Erik D. Demaine, Shay Mozes, Benjamin Rossman +1
Better Tradeoffs for Exact Distance Oracles in Planar Graphs
PaweÅ Gawrychowski, Shay Mozes, Oren Weimann +1
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter*n*log(n)) Time
Philip N. Klein, Shay Mozes
Near-Optimal Distance Emulator for Planar Graphs
Hsien-Chih Chang, PaweÅ Gawrychowski, Shay Mozes +1
Dispersion on Trees
PaweÅ Gawrychowski, Nadav Krasnopolsky, Shay Mozes +1
Faster Shortest Paths in Dense Distance Graphs, with Applications
Shay Mozes, Yahav Nussbaum, Oren Weimann
A new construction for a QMA complete 3-local Hamiltonian
Daniel Nagaj, Shay Mozes
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, PaweÅ Gawrychowski, Shay Mozes +1
Not So SuperDense Coding - Deterministic Dense Coding with Partially Entangled States
Shay Mozes, Benni Reznik, Jonathan Oppenheim
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
Glencora Borradaile, Philip N. Klein, Shay Mozes +2
Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time
Philip N. Klein, Shay Mozes
Near-Optimal Compression for the Planar Graph Metric
Amir Abboud, Pawel Gawrychowski, Shay Mozes +1
Efficient Vertex-Label Distance Oracles for Planar Graphs
Shay Mozes, Eyal E. Skop