Oren Weimann

Oren Weimann

Auto-generated profile, based on publicly available information

Oren Weimann

University of Haifa

Research Focus & Metrics

Academic Career Length

22Years (2005-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2015 in SIAM Journal on Computing
Verified
Journal Article
Closed access
Philip BillePhilip Bille
Philip Bille
GLGad M. Landau
Gad M. Landau
RRRajeev Raman
Rajeev Raman
KSKunihiko Sadakane
Kunihiko Sadakane
SSSrinivasa Rao Satti
Srinivasa Rao Satti
OWOren Weimann
Oren Weimann
Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with slight reduction in efficiency) many of the popular compression schemes, including the Lempel--Ziv family, run-length encoding, byte-pair encoding, Sequitur, and Re-Pair. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let $S$ be a string of length $N$ compressed into a context-free grammar $\mathcal{S}$ of size $n$. We present two representations of $\mathcal{S}$ achieving $O(\log N)$ random access time, and either $O(n\cdot\alpha_k(n))$ construction time and space on the pointer machine model, or $O(n)$ construction time and space on the RAM. Here, $\alpha_k(n)$ is the inverse of the $k$th row of Ackermann's function. Our representations also efficiently support decompression of any substring in $S$: we can decompress any substring of length $m$ in the same complexity as a single random access query and additional $O(m)$ time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern $P$ with at most $k$ errors in time $O(n(\min\{|P|k,k^4+|P|\}+\log N)+\mathrm{occ})$, where $\mathrm{occ}$ is the number of occurrences of $P$ in $S$. Finally, we generalize our results to navigation and other operations on grammar-compressed ordered trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two “biased” weighted ancestor data structures, and a compact representation of heavy paths in grammars.

28 December 2009 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
EDErik D. Demaine
Erik D. Demaine
SMShay Mozes
Shay Mozes
BRBenjamin Rossman
Benjamin Rossman
OWOren Weimann
Oren Weimann
The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. In this article, we present a worst-case O ( n 3 )-time algorithm for the problem when the two trees have size n , improving the previous best O ( n 3 log n )-time algorithm. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems, together with a deeper understanding of the previous algorithms for the problem. We prove the optimality of our algorithm among the family of decomposition strategy algorithms—which also includes the previous fastest algorithms—by tightening the known lower bound of Ω( n 2 log 2 n ) to Ω( n 3 ), matching our algorithm's running time. Furthermore, we obtain matching upper and lower bounds for decomposition strategy algorithms of Θ( nm 2 (1 + log n / m )) when the two trees have sizes m and n and m < n .

1 March 2013 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
OWOren Weimann
Oren Weimann
RYRaphael Yuster
Raphael Yuster
A distance sensitivity oracle of an n -vertex graph G = ( V , E ) is a data structure that can report shortest paths when edges of the graph fail. A query ( u ∈ V , v ∈ V , S ⊆ E ) to this oracle returns a shortest u -to- v path in the graph G ′ = ( V , E ∖ S ). We present randomized (Monte Carlo) algorithms for constructing a distance sensitivity oracle of size Õ ( n 3−α ) for | S | = O (lg n /lg lg n ) and any choice of 0 < α < 1. For real edge-lengths, the oracle is constructed in O ( n 4−α ) time and a query to this oracle takes Õ ( n 2−2(1−α)/|S| ) time. For integral edge-lengths in {− M ,..., M }, using the current ω < 2.376 matrix multiplication exponent, the oracle is constructed in O ( Mn 3.376−α ) time with Õ ( n 2−(1−α)/|S| ) query, or alternatively in O ( M 0.681 n 3.575−α ) time with Õ ( n 2−2(1−α)/|S| ) query. Distance sensitivity oracles generalize the replacement paths problem in which u and v are known in advance and | S | = 1. In other words, if P is a shortest path from u to v in G , then the replacement paths problem asks to compute, for every edge e on P , a shortest u -to- v path that avoids e . Our new technique for constructing distance sensitivity oracles using fast matrix multiplication also yields the first subcubic-time algorithm for the replacement paths problem when the edge-lengths are small integers. In particular, it yields a randomized (Monte Carlo) Õ ( Mn 2.376 + M 2 3 n 2.584 )-time algorithm for the replacement paths problem assuming M ≤ n 0.624 . Finally, we mention that both our replacement paths algorithm and our distance sensitivity oracle can be made to work, in the same time and space bounds, for the case of failed vertices rather than edges, that is, when S is a set of vertices and we seek a shortest u -to- v path in the graph obtained from G by removing all vertices in S and their adjacent edges.

1 January 2014
Verified
Book Chapter
Closed access
PDF file
AAAmir Abboud
Amir Abboud
VWVirginia Vassilevska Williams
Virginia Vassilevska Williams
OWOren Weimann
Oren Weimann

6 July 2020 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
KBKarl Bringmann
Karl Bringmann
PGPaweł Gawrychowski
Paweł Gawrychowski
SMShay Mozes
Shay Mozes
OWOren Weimann
Oren Weimann
The edit distance between two rooted ordered trees with n nodes labeled from an alphabet Ʃ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well-known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic O ( n 3 ) time and is based on a similar dynamic programming solution as string edit distance. In this article, we show that a truly subcubic O ( n 3-ε ) time algorithm for tree edit distance is unlikely: For |Ʃ| = Ω ( n ), a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For |Ʃ| = O (1), a truly subcubic algorithm for tree edit distance implies an O ( n k-ε ) algorithm for finding a maximum weight k -clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis (Backurs, Indyk STOC’15) whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.

1 March 2010 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PKPhilip N. Klein
Philip N. Klein
SMShay Mozes
Shay Mozes
OWOren Weimann
Oren Weimann
We give an O ( n log 2 n )-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s , finds the distances from s to all nodes.