GLGad M. Landau

Gad M. Landau

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Gad M. Landau has a total of 21 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Top Tree Compression of Tries

    by Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann


  • Open Access

    Top Tree Compression of Tries

    by Philip Bille, Inge Li Gørtz, Paweł Gawrychowski, Gad M. Landau, Oren Weimann

    We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supports efficient prefix search queries. Namely, we show how to preprocess a set of strings of total length $n$ over an alphabet of size $\sigma$ into a compressed data structure of worst-case optimal size $O(n/\log_\sigma n)$ that given a pattern string $P$ of length $m$ determines if $P$ is a prefix of one of the strings in time $O(\min(m\log \sigma,m + \log n))$. We show that this query time is in fact optimal regardless of the size of the data structure. Existing solutions either use $\Omega(n)$ space or rely on word RAM techniques, such as tabulation, hashing, address arithmetic, or word-level parallelism, and hence do not work on a pointer machine. Our result is the first solution on a pointer machine that achieves worst-case $o(n)$ space. Along the way, we develop several interesting data structures that work on a pointer machine and are of independent interest. These include an optimal data structures for random access to a grammar-compressed string and an optimal data structure for a variant of the level ancestor problem.

  • The nearest colored node in a tree

    by Paweł Gawrychowski, Gad M. Landau, Shay Mozes, Oren Weimann


  • Period recovery of strings over the Hamming and edit distances

    by Amihood Amir, Mika Amit, Gad M. Landau, Dina Sokol


  • Open Access

    String Cadences

    by Amihood Amir, Alberto Apostolico, Travis Gagie, Gad M. Landau

    We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the first interval must be the same length as the others. We give a sub-quadratic algorithm for determining whether a string has any cadence consisting of at least three occurrences of a character, and a nearly linear algorithm for finding all anchored cadences.

  • Open Access

    Longest Common Extensions in Trees

    by Philip Bille, Pawel Gawrychowski, Inge Li Goertz, Gad M. Landau, Oren Weimann

    The longest common extension (LCE) of two indices in a string is the length of the longest identical substrings starting at these two indices. The LCE problem asks to preprocess a string into a compact data structure that supports fast LCE queries. In this paper we generalize the LCE problem to trees and suggest a few applications of LCE in trees to tries and XML databases. Given a labeled and rooted tree $T$ of size $n$, the goal is to preprocess $T$ into a compact data structure that support the following LCE queries between subpaths and subtrees in $T$. Let $v_1$, $v_2$, $w_1$, and $w_2$ be nodes of $T$ such that $w_1$ and $w_2$ are descendants of $v_1$ and $v_2$ respectively. \begin{itemize} \item $\LCEPP(v_1, w_1, v_2, w_2)$: (path-path $\LCE$) return the longest common prefix of the paths $v_1 \leadsto w_1$ and $v_2 \leadsto w_2$. \item $\LCEPT(v_1, w_1, v_2)$: (path-tree $\LCE$) return maximal path-path LCE of the path $v_1 \leadsto w_1$ and any path from $v_2$ to a descendant leaf. \item $\LCETT(v_1, v_2)$: (tree-tree $\LCE$) return a maximal path-path LCE of any pair of paths from $v_1$ and $v_2$ to descendant leaves. \end{itemize} We present the first non-trivial bounds for supporting these queries. For $\LCEPP$ queries, we present a linear-space solution with $O(\log^{*} n)$ query time. For $\LCEPT$ queries, we present a linear-space solution with $O((\log\log n)^{2})$ query time, and complement this with a lower bound showing that any path-tree LCE structure of size $O(n \polylog(n))$ must necessarily use $\Omega(\log\log n)$ time to answer queries. For $\LCETT$ queries, we present a time-space trade-off, that given any parameter $\tau$, $1 \leq \tau \leq n$, leads to an $O(n\tau)$ space and $O(n/\tau)$ query-time solution. This is complemented with a reduction to the the set intersection problem implying that a fast linear space solution is not likely to exist.

  • Open Access

    Longest Common Extensions in Trees

    by Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann


  • Binary Jumbled Pattern Matching on Trees and Tree-Like Structures

    by Travis Gagie, Danny Hermelin, Gad M. Landau, Oren Weimann


  • Open Access

    Binary Jumbled Pattern Matching via All-Pairs Shortest Paths

    by Danny Hermelin, Gad M. Landau, Yuri Rabinovich, Oren Weimann

    In binary jumbled pattern matching we wish to preprocess a binary string $S$ in order to answer queries $(i,j)$ which ask for a substring of $S$ that is of size $i$ and has exactly $j$ 1-bits. The problem naturally generalizes to node-labeled trees and graphs by replacing "substring" with "connected subgraph". In this paper, we give an ${n^2}/{2^{\Omega(\log n/\log \log n)^{1/2}}}$ time solution for both strings and trees. This odd-looking time complexity improves the state of the art $O(n^2/\log^2 n)$ solutions by more than any poly-logarithmic factor. It originates from the recent seminal algorithm of Williams for min-plus matrix multiplication. We obtain the result by giving a black box reduction from trees to strings. This is then combined with a reduction from strings to min-plus matrix multiplications.

  • Open Access

    Tree Compression with Top Trees

    by Philip Bille, Inge Li Goertz, Gad M. Landau, Oren Weimann

    We introduce a new compression scheme for labeled trees based on top trees. Our compression scheme is the first to simultaneously take advantage of internal repeats in the tree (as opposed to the classical DAG compression that only exploits rooted subtree repeats) while also supporting fast navigational queries directly on the compressed representation. We show that the new compression scheme achieves close to optimal worst-case compression, can compress exponentially better than DAG compression, is never much worse than DAG compression, and supports navigational queries in logarithmic time.